c++字符串搜索之KMP

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;