类似Hdu3336
给出一个字符串，请算出它的每个前缀分别在字符串中出现了多少次。再将这些结果加起来输出
Input
The first line include a number T, means the number of test cases.
For each test case, just a line only include lowercase indicate the String S, the length of S will less than 100000.
Output
For each test case, just a number means the sum.
Sample Input
3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis
Sample Output
7
19
82
HINT
For the first case,
there are two "a","ac" and one "aca","acac","acacm" in the string "acacm".
So the answer is 2 + 2 + 1 + 1 + 1 = 7
Sol1:利用Kmp的性质,暴力统计,但是会TLE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll o,p[300011],sum[300011],len,ans,j;
char a[300011];
int main()
{
scanf("%lld",&o);
while(o--)
{
memset(p,0,sizeof(p));
memset(sum,0,sizeof(sum));
scanf("%s",a+1);
len=strlen(a+1);
ans=0;j=0;
for(ll i=1;i<len;i++)
{
while(j&&a[j+1]!=a[i+1])
j=p[j];
if(a[j+1]==a[i+1])
j++;
p[i+1]=j;
}
for(ll i=1;i<=len;i++)
{
sum[i]=1;
ll jj=i;
while (p[jj]!=0)
{
sum[i]++;
jj=p[jj];
}
ans=ans+sum[i];
}
printf("%lld\n",ans);
}
return 0;
}
Sol2:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll o,p[100011],sum[100011],len,ans,j; char a[100011]; int main() { scanf("%lld",&o); while(o--) { memset(p,0,sizeof(p)); memset(sum,0,sizeof(sum)); scanf("%s",a+1); len=strlen(a+1); ans=0;j=0; for(ll i=1;i<len;i++) { while(j&&a[j+1]!=a[i+1]) j=p[j]; if(a[j+1]==a[i+1]) j++; p[i+1]=j; } for(ll i=1;i<=len;i++) sum[i]=sum[p[i]]+1, ans+=sum[i]; printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/cutemush/p/12505574.html