28. Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

KMP算法實(shí)現(xiàn)

class Solution {
public:
    int strStr(string s, string m) {
        if(m.length() == 0)
            return 0;
        if(s.length() == 0||m.length() < 1 || s.length() < m.length())
            return -1;
        int si = 0;
        int mi = 0;
        vector<int> next = getNextArray(m);
        while(si < s.length() && mi < m.length()){
            if(s[si] == m[mi]){
                ++si;++mi;
            }else if (next[mi] == -1){
                ++si;
            } else {
                mi = next[mi];
            }
        }
        return mi == m.length() ? si - mi : -1;
    }

    vector<int> getNextArray(string ms){
        if(ms.length() == 1){
            return vector<int>(1,-1);
        }
        vector<int> next(ms.length());
        next[0] = -1;
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < next.size()){
            if (ms[pos - 1] == ms[cn])
                next[pos++] = ++cn;
            else if (cn > 0)
                cn = next[cn];
            else
                next[pos++] = 0;
            }
        return next;
    }
};