HDU 1711 Number Sequence （KMP）

白书说这个是MP，没有对f 数组优化过，所以说KMP有点不准确

#include <stdio.h>

int a,b;

int T[1000010],P[10010];//从0开始存

int f[10010];//记录P的自我匹配

void getFail(){

	int m=b;

	f[0]=f[1]=0;

	for(int i=1;i<m;i++){

		int j=f[i];

		while(j&&P[i]!=P[j])j=f[j];

		f[i+1]= P[i]==P[j] ? j+1 : 0;

	}

}

bool find(){

	int len1=a,len2=b;

	getFail();

	int j=0;

	for(int i=0;i<a;i++)

	{

		while(j&&P[j]!=T[i])j=f[j];

		if(P[j]==T[i])j++;

		if(j==b){printf("%d\n",i-b+2);return true;}

	}

	return false;

}

int main(){

	int cas,i;scanf("%d",&cas);

	while(cas--){

		scanf("%d%d",&a,&b);

		for(i=0;i<a;i++)scanf("%d",&T[i]);

		for(i=0;i<b;i++)scanf("%d",&P[i]);

		bool ans=find();

		if(ans==false)printf("-1\n");

	}

	return 0;

}

巴特西

HDU 1711 Number Sequence （KMP）

最新文章

热门文章