新版的一篇kmp算法莫名找不见了
HGU3336 Count the string
（超时的问题好久没解决）
题意
给出一个字符串，求它所有前缀在此字符串中出现的次数。
思路：从第一个字符开始，依次计算前缀个数，求和。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using
namespace
std
;
int
ne[
100
];
void GetNext(char* a)
{
int
len =
strlen
(a);
int
i =
0
, j =
-1
; ne[
0
] =
-1
;
while
(i < len){
if
(j ==
-1
|| a[i] == a[j]){ ne[++i] = ++j; }
else
j = ne[j]; }}
char
str[
100
];
int main()
{
int
T;
cin
>>T;
while
(T--) {
int
n,j,sum =
0
;
cin
>>n;
cin
>>str;
int
len =
strlen
(str); GetNext(str);
for
(
int
i = len ; i>=
1
; i--) { sum = (sum +
1
)%
10007
; j = ne[i];
while
(j) { sum = (sum +
1
)%
10007
; j = ne[j]; } }
memset
(ne,
0
,
sizeof
(ne));
cout
<<sum<<
endl
; }}
改了之后：
#include<cstdio>
#include<cstring>
#include<cstring>
#define N 200005
int next[N],dp[N];
char p[N];
void getnext(char *p)
{
int i=0,len=strlen(p);
int j=next[0]=-1;
while(i<len)
{
if(j==-1||p[i]==p[j])
{
i++,j++;
next[i]=j;
}
else
{
j=next[j];
}
}
}
int main()
{
int T,i,j,n,sum;
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof(dp));
scanf("%d %s",&n,p);
getnext(p);
sum = 0;
for(i=1; i<=n; i++)
{
dp[i]=dp[next[i]]+1;
sum=(sum+dp[i])007;
}
printf("%d\n",sum);
}
return 0;
}
