class Solution
{
private:
void getNext(int* arr, string str) {
int len = str.length();
arr[0] = 0;
int j = 0;
for (int i = 1; i < len; i++)
{
while (j > 0 && str[i] != str[j]) {
j = arr[j - 1];
}
if (str[i] == str[j]) {
j++;
}
arr[i] = j;
}
}
public:
int indexOf(string haystack, string needle) {
int needleLen = needle.length();
int haystackLen = haystack.length();
int* next = new int[needleLen];
getNext(next, needle);
for (int i = 0; i < haystackLen; i++) {
if (haystack[i] == needle[0]) {
int j = 1;
while (j < needleLen && j > 0) {
if (haystack[++i] != needle[j++]) {
j = next[j - 2];
i--;
}
}
if (j == needleLen)return i-needleLen+1;
}
}
return -1;
}
};
//KMP
string haystack = "aabaabaafa";
string needle = "aabaaf";
int res = s1.indexOf(haystack, needle);
cout << "your answer is: " << res << " it's " <<
((res == 3) ? "correct!" : "wrong!!!")
<< endl;