# My C++ brute-force, Robin-Karp, KMP codes

• Brute-force version

``````class Solution {
public:
int strStr(string haystack, string needle) {
int i, hSize = haystack.size(), nSize = needle.size();
if(hSize<nSize) return -1;
if(!nSize) return 0;
for(i=0; i<=hSize-nSize && haystack.substr(i,nSize)!= needle;++i);
return i<=hSize-nSize?i:-1;
}
};
``````

Robin-Karp version (followed WiKI with a simple hash function, https://en.wikipedia.org/wiki/Rabin–Karp_algorithm)

``````class Solution {
private:
inline char hash(const string &s)
{
char all =0;
for(auto i=0;i<s.size();++i)    all ^=s[i];
return all;
}

public:
int strStr(string haystack, string needle) {
int i, hSize = haystack.size(), nSize = needle.size();
char target;
if(hSize<nSize) return -1;
if(!nSize) return 0;
target = hash(needle);
for(i=0; i<=hSize-nSize;++i)
{
if(hash(haystack.substr(i,nSize)) == target && haystack.substr(i,nSize)== needle) break;
}
return i<=hSize-nSize?i:-1;
}
};
``````

Standard KMP algorithm (followed Wiki, https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm)

``````   class Solution {
private:
void buildKMPTable(const string & s, vector<int> &KMP_Table)
{
int sSize = s.size(), i=2, j=0;
KMP_Table[0] = -1;
if(sSize>1) KMP_Table[1] = 0;
while(i<sSize)
{
if(s[i-1]==s[j]) KMP_Table[i++] = ++j;
else if(j>0) j = KMP_Table[j];
else KMP_Table[i++] = 0;
}
}
public:
int strStr(string haystack, string needle) {
int start=0, i=0, hSize = haystack.size(), nSize = needle.size();
if(hSize<nSize) return -1;
if(!nSize) return 0;
vector<int> KMP_Table(nSize, 0);
buildKMPTable(needle, KMP_Table);
while(start<=hSize-nSize)
{
if(haystack[start+i]==needle[i])
{
if(++i == nSize) return start;
}
else
{
start = start+i-KMP_Table[i];
i= i>0?KMP_Table[i]:0;
}
}
return -1;
}
};``````

• Hi, I have a question for your Rolling Hash algorithm, why you ^ all elements in the array to get the hash? Thanks

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.