# Simple Solution with Hash cpp

• The first method came into my mind is O(nm) brute-force, but it's TLE.
The second method is KMP, but I can't write it quickly and clearly.
The third method is Hash, which is easy to implement.

We need a Hash to calculate continuous sequence of chars, and the hash can be updated quickly when removing or adding new char at the head and tail of the string. The simplest one is XOR.

``````unsigned int strHash(string str){
unsigned int res = 0;
for (int i = 0; i < str.size(); i++)
res ^= str[i];
return res;
}

unsigned int updateHash(char in, char out, unsigned int hashval){
hashval ^= in;
hashval ^= out;
return hashval;
}

int strStr(string haystack, string needle) {
if (haystack.size() < needle.size()) return -1;
int i, j;
unsigned int tar, val;
tar = strHash(needle);
val = strHash(haystack.substr(0, needle.size()));
i = 0;
while(true){
if (tar == val){
for (j = 0; j < needle.size(); j++)
if (haystack[i + j] != needle[j]) break;
if (j == needle.size()) return i;
}
if (i + needle.size() >= haystack.size()) break;
val = updateHash(haystack[i + needle.size()], haystack[i], val);
i++;
}
return -1;
}
``````

This hash is too simple to fail in this case:

aaaaaaaaaaaaaaaaaaaaaaaaaaa...., bbbbbbbbbbbbbbbbb...(even number of 'b')

Because the hash value will be 0.