kmp板子+扩展kmp

洛谷模板题
求出s2在s1中所有出现的位置，以及next【i】数组
next数组是指a的前缀和以i结尾的a的后缀的最大匹配

#include<cstdio>
#include<cstring>
const int maxn=1000005;
int next[maxn],f[maxn];
int main(){
   
	char a[maxn],b[maxn];//b是长的，a是短的
	scanf("%s%s",b+1,a+1);
	int n=strlen(a+1);
	int m=strlen(b+1);
	next[1]=0;
	for(int i=2,j=0;i<=n;i++){
   
		while(j>0&&a[i]!=a[j+1])	j=next[j];
		if(a[i]==a[j+1])	j++;
		next[i]=j;
	}
	for(int i=1,j=0;i<=m;i++){
   
		while(j>0&&(j==n||b[i]!=a[j+1]))	j=next[j];
		if(b[i]==a[j+1])	j++;
		f[i]=j;
		if(f[i]==n)	printf("%d\n",i-n+1);
	}
	
	printf("%d",next[1]);
	for(int i=2;i<=n;i++)
		printf(" %d",next[i]);
	return 0;
} 

扩展kmp
next数组是指a的前缀和以i为开始的前缀的最大匹配.

const int maxn=100010;
int next[maxn],ex[maxn];
void getNext(char *str){
   
    int i=0,j,po,len=strlen(str);
    next[0]=len; 
    while(str[i]==str[i+1]&&i+1<len) i++; 
	next[1]=i; 
    po=1; 
    for(i=2;i<len;i++){
   
        if(next[i-po]+i<next[po]+po) 
            next[i]=next[i-po];
        else{
   
            j=next[po]+po-i;
            if(j<0) j=0; 
            while(i+j<len&&str[j]==str[j+i]) j++; next[i]=j;
            po=i; 
        }
    }
}
void EXKMP(char *s1,char *s2){
   
    int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    getNext(s2); 
    while(s1[i]==s2[i]&&i<l2&&i<len) i++; 
	ex[0]=i;
    po=0; 
    for(i=1;i<len;i++){
   
        if(next[i-po]+i<ex[po]+po) 
            ex[i]=next[i-po];
        else{
   
            j = ex[po]+po-i;
            if(j<0) j=0; 
            while(i+j<len&&j<l2&&s1[j+i]==s2[j]) j++; ex[i]=j;
            po=i; 
        }
    }
}