Implement Strstr

虽然leetcode标示这个问题是easy，但是字符串查找是一个很经典的问题。有很多种解决方案，所以我还是认为是Hard。

KMP

做了好多遍的next数组求解，终于记住了next数组怎么操作！

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack.size()<needle.size())return -1;

        if(needle.size()==0)return 0;

        vector<int> next=getNext(needle);

        int si=0,sj=0;
        while(si<(int)haystack.size() && sj<(int)needle.size())
        {
            if(sj==-1 || haystack[si]==needle[sj])
            {
                si++;
                sj++;
            }
            else
            {
                sj=next[sj];
            }
        }

        if(sj==needle.size())return si-sj;
        else return -1;
    }
    vector<int> getNext(string &p)
    {
        vector<int> next(p.length());

        next[0]=-1;
        int i=0,j=-1;

        while(i<p.length()-1)
        {
            while(j!=-1 && p[i]!=p[j])j=next[j];

            i++;j++;

            if(p[i]==p[j])next[i]=next[j];
            else next[i]=j;
        }

        return next;
    }
};