hust 1328 String

题目描述

Give you a string S,assume the Sub-String Stri = S[0..i] and the length of the string is N. e.g. S = "moreandmorecold", N = 15, Str0 = "m" Str1 = "mo" Str2 = "mor" and so on. And we define c[i] indicate how many Sub-String Stri in S, now please calculate the sum of c[0] to c[N-1].

输入

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.

输出

Fore each test case, just a number means the sum.

样例输入

3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis

样例输出

7
19
82

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

简单的kmp算法应用
详见 http://blog.csdn.net/hcbbt/article/details/17058857

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
char p[100001];
int f[100002];
void getf()
{
    int m=strlen(p);
    f[0]=f[1]=0;
    for (int i=1;i<m;i++)
    {
        int j=f[i];
        while(j && p[i]!=p[j]) j=f[j];
        f[i+1]=(p[i]==p[j]?j+1:0);
    }
}
int main()
{
    int n,len;
    long long sum[100001],ans;
    scanf("%d
",&n);
    while (n--)
    {
        ans=0;
        gets(p);getf();len=strlen(p);
        memset(sum,0,sizeof(sum));
        for (int i=1;i<=len;i++)
        {
            sum[i]=sum[f[i]];
            sum[i]++;
            ans+=sum[i];
        }
        printf("%lld
",ans);
    }
    return 0;
}