KMP（模板）

简单理解 首先kmp有两部分组成

第一部分 next数组

什么是next数组

通俗的讲就是 子串自己对自己的前后缀匹配

举个栗子

子串：ABABCABAA

对应的next

第二部分就是kmp了

其实跟第一部分很像，只不过是把对象换成了母串

即子串对母串的前缀匹配

落谷有一kmp模板题点这里

# 下面是蒟蒻的代码以及巨佬的代码

//鄙人的代码，只能过70%的样例，剩下的超时了很尴尬
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char a[2222222],b[2222222];
int p[2222222];
void next(int lenb)
{
	p[0]=0;//第一个为0 
	int i=1,len=0;//i是位置，len是长度 
	while(i<lenb)//自我匹配 
	{
		if(b[i]==b[len]){
			len++;
			p[i++]=len;	
		}
		else
		{
			if(len>0)//防止出现死循环 
				len=p[len];//跳回去 
			else
				p[i++]=len; 		
		}
	}
}
void move(int lenb)//这个函数是让next数组向后移一位，并把第一位设为-1 
{
	int i;
	for(i=lenb;i>0;i--)
		p[i]=p[i-1];
		p[0]=-1;
}
void kmp(int lena,int lenb)
{
	int i=0,j=0;
	next(lenb);
	move(lenb);
	while(i<lena)
	{
		if(j==lenb-1&&a[i]==b[j])//这里是判断是否有完全匹配的情况
		{
			printf("%d\n",i-j+1);  //如果有 输出位置
			j=p[j];//继续往下匹配 
		}
		if(a[i]==b[j])
		{
			i++;j++;
		}
		else
		{
			j=p[j];
			if(j==-1)//防止出现死循环 
			{
				i++;j++;
			}
		}
	}
}
int main()
{
	scanf("%s%s",&a,&b);
	int lena=strlen(a),lenb=strlen(b);	 
	kmp(lena,lenb);
	for(int i=1;i<=strlen(b);i++)
	printf("%d ",p[i]);	
	return 0;
} 

//巨佬的代码，可AC
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char a1[2000000],a2[2000000];
int kmp[2000000];
int main()
{
    scanf("%s%s",a1,a2);
    kmp[0]=kmp[1]=0;//前一位，两位失配了，都只可能将第一位作为新的开头
    int len1=strlen(a1),len2=strlen(a2);
    int k;
    k=0;
    for(int i=1;i<len2;i++)//自己匹配自己
    {
        while(k&&a2[i]!=a2[k]) k=kmp[k];//找到最长的前后缀重叠长度
    	//不相等的情况，即无前缀能与后缀重叠，直接赋值位0（注意是给下一位，因为匹配的是下一位适失配的情况）
    	if(a2[i]==a2[k])
    	{
    		k++;
			kmp[i+1]=k; 
		}
		else
		kmp[i+1]=0;
	}
    k=0;
    for(int i=0;i<len1;i++)
    {
        while(k&&a1[i]!=a2[k]) k=kmp[k];//如果不匹配，则将利用kmp数组往回跳
    		//如果相等了，则匹配下一位
        if(a1[i]==a2[k])
        	k++;
				
		if(k==len2)
		printf("%d\n",i-len2+2);//如果已经全部匹配完毕，则输出初始位置
    }
    for(int i=1;i<=len2;i++)
	printf("%d ",kmp[i]);//输出数组
    return 0;
}