class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        int i, q;
        int *next = new int[m];
        getNext(needle, next);
        for(i = 0, q = 0; i < n; i++){
            while(q > 0 && haystack[i] != needle[q])
                q = next[q-1];
            if(haystack[i] == needle[q])
                q++;
            if(q == m)
                return i-q+1;
        }
        return -1;
    }    
    void getNext(const string& pattern, int next[]){
        int m = pattern.size();
        int k;
        next[0] = 0;
        for(int q = 1, k = 0; q < m; q++){
            while(k > 0 && pattern[q] != pattern[k])
                k = next[k-1];
                /*pattern[0...k-1]能匹配，pattern[k]待匹配 ,不行就再缩小k的范围*/
            if(pattern[q] == pattern[k])
                k++;
            next[q] = k;
        }
        /*经典示例：ababzababa */
    }
};