KMP算法

class Solution {
public:
    void getNext(int* next,const string& s)
    {
        int j = 0;//前缀的末尾，统一0操作，所以初始化为0
        next[0] = j;
        for(int i = 1; i < s.size(); i++)
        {
            先处理前后缀不相等的情况，如果不相等，前缀要进行回退，知道回退到相等或者到模式串开头位置，回退的下标就是当前前缀前一个位置的next数组的值
            while(j > 0 && s[i] != s[j])
            {
                j = next[j-1];
            }
            处理前后缀相同的情况，如果相同，i和j都往后移一位，j++,next[i]等于j
            if(s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

    int strStr(string haystack,1)">string needle) {
        haystack是文本串
        needle是模式串
        KMP算法，需要构造next数组
       if(needle.size() == 0)
       {
           return ;
       }
       int next[needle.size()];
       getNext(next,needle);得到前缀表
       得到前缀表之后，需要进行匹配，用j来迭代模式串，用i来迭代文本串
       因为next数组里是从0开始的
       0; i < haystack.size(); i++先处理二者不相等的情况，如果不相等，模式串需要回退，按照next数组进行回退
           0 && haystack[i] != needle[j])
           {
               j = next[j-];
           }
           如果二者相等，继续向后判断
           if(haystack[i] == needle[j])
           {
               j++;i++在循环里头
           }
           判断是不是模式串在文本串里头的条件：迭代器j已经到了尾部
           if(j == needle.size())
           {
               return i - needle.size() + ;
           }
       }
       return -;
    }
};