HDU—3336KMP性质简单应用
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3336
题意:首先给个T:有几组测试数据
对于每个测试数据:给一个数字m为串的长度,给一串m个字符长度的串
求:对于串的每一个前缀,其在串中出现次数的总和并mod10007(在这里出错了)
题目给了一个例子:对于4长度的串abab ,有"a","ab","aba","abab"共四个前缀
“a“出现了2次,"ab" : 2,"aba":1,"abab":1,所以共2+2+1+1=6次。
一开始感觉它实际上再利用KMP的性质(不懂KMP的请另行查阅资料),尝试一下就A了,比如在某处失配会有j = next[j]的操作,
其实也就说明了字符串有重叠的部分,详见下图说明,写的有点乱,按顺序看完应该就懂了(从黑笔看再看蓝笔):
代码如下:
#include <iostream>#include <string.h>
#include <stdio.h>
using namespace std;
const int MAXN =200006;
const int MOD = 10007;
int n,m;
int ne[MAXN];
char p[MAXN],arr[MAXN];
void get_ne()//求next数组
{
int i,j;
j=ne[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&p[i]!=p[j]) j=ne[j];
ne[++i]=++j;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&m,p);
get_ne();
int ans=0;
for(int i=m;i>=0;i--)//上图模拟部分的代码实现
{
int j=i;
while(j!=0)
{
ans++;
j=ne[j];
}
}
printf("%d\n",(ans%MOD));
}
return 0;
}