KMP算法

原理见知乎：

https://www.zhihu.com/question/21923021/answer/281346746?utm_psn=1900243304974652304

寻找第一次出现的位置：

class Solution {
public:int kmp(string haystack, string needle) {int m=haystack.size(),n=needle.size();vector<int>next(n+1);int i=0,j=-1;next[0]=-1;while(i<n){if(j==-1||needle[i]==needle[j]){i++;j++;next[i]=j;}else j=next[j];}i=0,j=0;while(i<m&&j<n){if(j==-1||haystack[i]==needle[j]){i++;j++;}else j=next[j];}if(j!=n)return -1;return i-j;}
};

寻找全部出现的位置：

class Solution {
public:vector<int> kmp(string haystack, string needle) {int m=haystack.size(),n=needle.size();vector<int>next(n+1);int i=0,j=-1;next[0]=-1;while(i<n){if(j==-1||needle[i]==needle[j]){i++;j++;next[i]=j;}else j=next[j];}i=0,j=0;vector<int>res;while(i<m){if(j==-1||haystack[i]==needle[j]){i++;j++;}else j=next[j];if(j==n){res.push_back(i-j);i-=j-1;j=0;}}return res;}
};