LeetCode:implement strstr C# https://leetcode.com/problems/implement-strstr/

I implemented Rabin-Karp algorithm
https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

please review for performance, also if you were in an interview what do you think about using functions like GetHashCode()?
would you like the interviewee to implement the hashing on their own?


  Implement strStr().
  
  Return the index of the first occurrence of needle in haystack, or -1
  if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

  
  What should we return when needle is an empty string? This is a great
  question to ask during an interview.
  
  For the purpose of this problem, we will return 0 when needle is an
  empty string. This is consistent to C's strstr() and Java's indexOf().


using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{
    /// &lt;summary&gt;
    ///https://leetcode.com/problems/implement-strstr/
    /// &lt;/summary&gt;
    [TestClass]
    public class StrStrLeetCode
    {
        [TestMethod]
        public void ValidNeedleTest()
        {
            string haystack = "hello";
            string needle = "ll";
            Assert.AreEqual(2, StrStr(haystack, needle));
        }

        [TestMethod]
        public void NotValidNeedleTest()
        {
            string haystack = "aaaaa";
            string needle = "ba";
            Assert.AreEqual(-1, StrStr(haystack, needle));
        }



        public int StrStr(string haystack, string needle)
        {
            if (string.IsNullOrEmpty(needle))
            {
                return 0;
            }
            int n = haystack.Length;
            int m = needle.Length;
            var hash = needle.GetHashCode();
            for (int i = 0; i &lt; n - m + 1; i++)
            {
                string tempStr = haystack.Substring(i, m);
                var hashTemp = tempStr.GetHashCode();
                if (hash == hashTemp)
                {
                    return i;
                }
            }

            return -1;
        }
    }
}
As dfhwze and Roland already pointed out, a hash alone is not sufficient to determine whether two things are equal, so you still need to do a string comparison afterwards if the hashes match. Otherwise you will get wrong results from time to time. Not to mention the effect of hash randomization between different application runs...

The idea behind Rabin-Karp's use of hashes is to replace costly string comparisons with cheap hash comparisons. But in your case, the cost of creating a substring and calculating its hash (which involves some calculations for every character) is often greater than doing a direct string comparison (which can bail out at the first difference).

As the Wikipedia article that you linked to says, you'll want to use a rolling hash, a hashing algorithm that allows you to calculate the hash of the next substring with just a few operations, regardless of how long that substring is.



Also, as far as I can tell, storing string.Length in a local variable doesn't offer any performance improvements. It does make the code slightly less readable though, in my opinion.