kmp 模板

发布于 2022-02-28  80 次阅读


#include <iostream>
#include <string.h>
using namespace std;

const  int N = 1e6+10;

char s[N],t[N];
int nextt[N];
int len1,len2,cnt = 0;
int cun[N];
void get_nextt()
{
	int i=0,j=-1;
	nextt[0]=-1;
	while(i<len1)
	{
		if(j==-1||t[i]==t[j])nextt[++i]=++j;
		else
		j = nextt[j];
	}
}

void kmp()
{
	int i=0,j=0;
	get_nextt();
	while(i<len2)
	{
		if(s[i]==t[j]||j==-1)++i==++j;
		else 
		j=nextt[j];
		if(j == len1)
		{
		    cun[cnt]=i-len1;
		    cnt++;
		}
			
	}
}



int main()
{
	int a,b;
	scanf("%d %s",&a,t);
	scanf("%d %s",&b,s);
	len1 = a;
	len2 = b;
	kmp();
	for(int i=0;i<cnt;i++)cout<<cun[i]<<" ";
	return 0;
}