hdu 1711 Number Sequence （ KMP算法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1711

 

解题报告：一道比较简单的kmp题目，还是很佩服当初发明者个算法的一群人，怎么想到的next数组的写法，让我们这帮菜鸟反复理解其含义。不知道为什么这么写，但我们至少要理解next的含义。

 

首先：next[0]=-1 ，是我们规定的每个串的第一个值为-1；

 

其次： next[j]=-1，这儿有两种可能。

第一，第j个元素的值和第一个元素的值相等 且 J前面的k个元素与前1~k个元素不相等。

第二，前面的1~k个元素与j前面的k个元素相等，但是next[j]==next[k]。

如abcabcad中next[6]=-1,因为a[3]=a[6] ；

 

再次：next[j]=k的情况。前面的1~k个元素与j前面的k个元素相等，但是next[j]！=next[k]。

 

 最后：next[j]=0：除了上述的三种情况。

 

 

#include<cstdio>
#include<cstring>
using namespace std;
const int MAX2 = 10000+5;
const int MAX1 = 1000000+5;

int n,m;
int next[MAX2],b[MAX2],a[MAX1];

void get_next()
{
	int j=-1,i;
	next[0]=-1;
	for(int i=1;i<=m;i++)
	{
		while(j>-1&&b[j+1]!=b[i])
		{
			j=next[j];
		}
		if(b[j+1]==b[i])
			j++;
		next[i]=j;
	}
}

int KMP()
{
	get_next();
	int j=-1,cnt=0,i,pos=0;
	for(int i=0;i<n;i++)
	{
		while(j>-1&&b[j+1]!=a[i])
		{
			j=next[j];
		}
		if(b[j+1]==a[i])
			j++;
		if(j==m-1)
		{
			pos=i;
			cnt=j;
			break;
		}
	}
	if(pos != 0) return pos-cnt+1;
	return -1;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(int j=0;j<m;j++)
			scanf("%d",&b[j]);
		int ans = KMP();
		printf("%d\n",ans);
	}
	return 0;
}