KMP 模板

题目描述

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

char s1[N],s2[N];
int nexti[N];
int len1, len2;

void calc_next(){
	int t1=0,t2=-1;
	nexti[0]=-1;
	while(t1<len2){
		if(t2==-1 || s2[t1]==s2[t2])
			nexti[++t1]=++t2; // 计算最长公共前后缀
		else
			t2=nexti[t2];
	}
}

void kmp(){
	int t1=0,t2=0;
	while(t1<len1){
		if(t2==-1 || s1[t1]==s2[t2]){ //可以匹配
			t1++;
			t2++;
		}
		else
			t2=nexti[t2]; //jump
		if(t2==len2){
			cout<<t1-len2+1<<endl;
			t2=nexti[t2];
		}
	}
}

int main(){
	scanf("%s",s1);
	scanf("%s",s2);
	len1 = strlen(s1);
	len2 = strlen(s2);
	calc_next();
	kmp();
	for(int i=1;i<=len2;i++){
		printf("%d ",nexti[i]);
	}
}