28. Implement strStr()

KMP

算法导论P1006 running-time analysis

class Solution {
public:
    void computePrefix(string &p, vector<int> &next) {
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < p.size(); i++) {
            while (k >= 0 && p[k + 1] != p[i])
                k = next[k];
            if (p[k + 1] == p[i]) k++;
            next[i] = k;
        }
        //for (int i = 0; i < p.size(); i++) cout<<next[i]<<' ';cout<<endl;
    }
    int strStr(string haystack, string needle) {
        if (!needle.size()) return 0; 
        string s = haystack;
        string p = needle;
        vector<int> next(p.size(), 0);

        computePrefix(p, next);

        //KMP
        int k = -1;
        for (int i = 0; i < s.size(); i++) {
            while (k >= 0 && s[i] != p[k + 1])
                k = next[k];
            if (s[i] == p[k + 1]) k++;
            if (k == p.size() - 1) return i - k;
            //cout<<i<<' '<<k<<endl;
        }
        return -1;
    }
};