3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis
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\n",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\n",ans); 28 } 29 return 0; 30 }
原文：https://www.cnblogs.com/cutepota/p/12555570.html