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].
给出一个字符串，请算出它的每个前缀分别在字符串中出现了多少次。再将这些结果加起来输出

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:先求出next[]数组值，建fail树求出每个结点为根的子树个数，加起来即为答案，具体如下：



树中每个结点都是整个字符串的前缀，对于每条链，父亲结点既是儿子的前缀，也是后缀，我们要统计每个结点出现的次数，就是统计以该结点为根的子树的结点个数。上例中，1结点为根的子树结点数为3，即a出现了3次。我们建立fail树后，做dfs（）即可求出子树大小。

sol2:求出next[]后，逆循环扫一遍。

做dfs()，我们要重复计算多次，更推荐的方法是从下往上做逆循环，这样做过的事情就不会再做。逆循环时，父亲结点编号小，儿子结点编号大，儿子结点为根的子树个数与父亲结点先计算出来。



代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll o,p[100011],sum[100011],len,ans,j;
 5 char a[100011];
 6 int main()
 7 {
 8     scanf("%lld",&o);
 9     while(o--)
10     {
11         memset(p,0,sizeof(p));
12         memset(sum,0,sizeof(sum));
13         scanf("%s",a+1);
14         len=strlen(a+1);
15         ans=0;j=0;
16         for(ll i=1;i<len;i++)
17         {
18             while(j&&a[j+1]!=a[i+1])
19                 j=p[j];
20             if(a[j+1]==a[i+1])
21                 j++;
22             p[i+1]=j;
23         }
24         for (int i=1;i<=len;i++)
25         sum[i]=1; 
26         for(ll i=len;i>=1;i--)
27             sum[p[i]]+=sum[i];
28         for (int i=1;i<=len;i++)
29             ans=ans+sum[i];
30         printf("%lld
",ans);
31     }
32     return 0;
33 }

当然，也可以写成正循环，如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll o,p[100011],sum[100011],len,ans,j;
 5 char a[100011];
 6 int main()
 7 {
 8     scanf("%lld",&o);
 9     while(o--)
10     {
11         memset(p,0,sizeof(p));
12         memset(sum,0,sizeof(sum));
13         scanf("%s",a+1);
14         len=strlen(a+1);
15         ans=0;j=0;
16         for(ll i=1;i<len;i++)
17         {
18             while(j&&a[j+1]!=a[i+1])
19                 j=p[j];
20             if(a[j+1]==a[i+1])
21                 j++;
22             p[i+1]=j;
23         }
24         for(ll i=1;i<=len;i++)
25             sum[i]=sum[p[i]]+1,
26             ans+=sum[i];
27         printf("%lld
",ans);
28     }
29     return 0;
30 }