HDU 3336 Count the string

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

这个题目是扩展KMP next数组的一个应用，非常的灵活。扩展KMP next数组的定义为以i为起点的后缀能与原字符串的最大匹配长度，其中nex[i]的值其实就表示它的后缀所匹配的前缀数量。例如nex[0]=len,其实他匹配了字符串c的所有前缀，而字符串c的前缀个数就是它的长度。与这个题完美契合。

如果对扩展KMP不太理解可以去看这个博客里附的PPT->here

贴个代码：

#include<bits/stdc++.h>
using namespace std;
const int SIZE=200005;
int nex[SIZE],n,m;
char t[SIZE];
long long ans=0;

void getnext(){
	int a,p,i,j(-1);
	nex[0]=m;
	ans=m;
	for(int i=1;i<m;++i,--j){
		if(j<0||i+nex[i-a]>=p){
			if(j<0)j=0,p=i;
			while(p<m&&j<m&&t[p]==t[j])
			p++,j++;
			nex[i]=j,a=i;
		}
		else nex[i]=nex[i-a];
		ans+=nex[i];
		ans%=10007;
	}
}

int main(){
	int f;
	cin>>f;
	while(f--){
		cin>>n;
		scanf("%s",t);
		m=strlen(t);
		getnext();
		printf("%I64d\n",ans);
	}
}