KMP模式匹配算法+ACwing831KMP字符串

模式匹配算法是很低效的，于是有三位前辈，D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特—莫里斯—普拉特算法，简称KMP算法。

朴素模式匹配算法的复杂度是O(N*M)，但KMP模式匹配的时间复杂度是O(N)，因为n（主串的长度）不需要回溯，要进行匹配的串不停的移动和主串对比，匹配串也不用每次都从头开始比，而是先对匹配串计算出next数组，用next数组进行回溯。

首先看一个例子，比如主串为s：ababacda,匹配串为p：abababc,在下标为六位置的时候s[i]!=p[i],按照模式匹配我们将从s的下标为二，p的第一个再重复上面步骤去比，但其实，当我们知道s和p的前五个相同为ababa，那么再让s的下标为2的位置(b)去和p的下标为1的位置(a)去比，是可以省略的，因为肯定不相等，而且很明显我们可以直接从s的下标为3的位置(a)开始。而KMP的next数组存的就是以匹配串的第j个位置为终点的后缀与以匹配串的起点开始的前缀相同的最大长度是多少，这样在发现s[i] 不等于p[j+1]时可以回溯，让j=next[j]，而不是总回到第一个位置开始比较。

图解：

#include
using namespace std;
const int N=100010,M=1000010;
char s[M],p[N];
int ne[N];
int n,m;
int main(){
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0;i<=n;i++){//获得ne数组
        while(j&&p[i]!=p[j+1]) j=ne[j];//如果下一个后缀不相同就让j回溯
        if(p[i]==p[j+1]) j++;//如果相同就说明前缀和后缀相同的字符数多了一个，j继续往后比较下一个
        ne[i]=j;//当前j的值就是截止到第i个字符前缀和后缀最大相同数
    }
     //KMP匹配过程
    for(int i=1,j=0;i<=m;i++){
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n){//匹配成功
            printf("%d ",i-n);//输出下标
            j=ne[j];//主串只要还没遍历完就继续回溯
        }
    }
}

今日LeetCode没刷题呜呜呜呜，但搞懂了一个kmp算法也是很开心的呀！明天见~（欢迎留言讨论）