luogu3375 【模板】KMP字符串匹配

nxt数组下标从1开始而a，b数组下标从0开始。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int lena, lenb, nxt[1000005];

char a[1000005], b[1000005];

void mknxt(){

	int j=0, k;

	k = nxt[0] = -1;

	while(j<lenb){

		if(k==-1 || b[j]==b[k])	nxt[++j] = ++k;

		else	k = nxt[k];

	}

}

void kmp(){

	int i=0, j=0;

	while(i<lena){

		if(j==-1 || a[i]==b[j])	i++, j++;

		else	j = nxt[j];

		if(j==lenb)	printf("%d\n", i-j+1), j = nxt[j];

	}

}

int main(){

	scanf("%s %s", a, b);

	lena = strlen(a);

	lenb = strlen(b);

	mknxt();

	kmp();

	for(int i=1; i<=lenb; i++)	printf("%d ", nxt[i]);

	return 0;

}

巴特西

luogu3375 【模板】KMP字符串匹配

最新文章

热门文章