hdu 3336 Count the string （KMP算法）

http://acm.hdu.edu.cn/showproblem.php?pid=3336

 

解题报告：刚开始用的是暴力的方法，就是每次往next数组中加一个元素，然后再在整个数组中进行查找，虽然加了很多的优化，但是还是无限的TLE中。（拒绝暴力，另寻他路）。

直接用next数组的意义，不过这次的求解next的方法与上次有些不同，暂且叫作方法二吧：

 

void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<n)
	{
		while(j>-1&&a[j]!=a[i])
		{
			j=next[j];
		}
		i++;	
		j++;
		next[i]=j;
		printf("next[%d]=%d\n",i,next[i]);
	}

}

 与原来的算法有什么不同呢？虽然也定义next[0]=-1,但后面绝不会出现-1，除了next[0]，其他模式值next[j]=k(0≤k<j)的意义可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求a[j]!=a[k]。其实next[0]也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next[0]=0的），这样，next[j]=k(0≤k<j)的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的个字符相同。这样子问题就简单多了！

 

#include<cstdio>
#include<cstring>
using namespace std;

const int MAX =200000+5; 
char a[MAX];
int next[MAX],n;

void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<n)
	{
		while(j>-1&&a[j]!=a[i])
		{
			j=next[j];
		}
		i++;	
		j++;
		next[i]=j;
		printf("next[%d]=%d\n",i,next[i]);
	}

}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int ans=0;
		scanf("%d %s",&n,a);
		get_next();
		ans+=n+next[n];
		for(int i=0;i<n;i++)
		{
			if(next[i]>0&&next[i]+1!=next[i+1])
			{
				ans+=next[i];
			}
		}
		printf("%d\n",ans%10007);
	}
	return 0;
}