Description
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
Fore each test case, just a number means the sum.
Sample Input
3 acacm moreandmorecold thisisthisththisisthisisthisththisis
Sample Output
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
题意：给定一个串，求前缀在串中出现次数之和。
解题思路：假设字符串的长度为n，首先肯定会有n个串出现，剩下的部分就是中间一些串可能与前面的相同，这个根据
每一个后缀与后缀0的最长公共前缀叠加得出。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-29 20:43:51
File Name :4.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=300300;
int height[maxn],sa[maxn],rank[maxn],c[maxn],t1[maxn],t2[maxn];
void da(int *str,int n,int m)
{
int i,j,k,p,*x=t1,*y=t2;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=str[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1)
{
p=0;
for(i=n-k;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[y[i]]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
if(p>=n)break;
m=p;
}
}
void calheight(int *str,int n)
{
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++)
{
if(k)k--;
j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
// printf("sa:");for(i=0;i<=n;i++)printf("%d ",sa[i]);puts("");
// printf("rank:");for(i=0;i<=n;i++)printf("%d ",rank[i]);puts("");
// printf("height:");for(i=0;i<=n;i++)printf("%d ",height[i]);puts("");
}
int str[maxn];
char ss[maxn];
int Log[maxn];
int best[23][maxn];
void init(int n)
{
int i,j;
Log[0]=-1;
for(i=1;i<=n;i++)
Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
for(i=1;i<=n;i++)best[0][i]=height[i];
for(i=1;i<=Log[n];i++)
for(j=1;j<=n;j++)
best[i][j]=min(best[i-1][j],best[i-1][j+(1<<(i-1))]);
}
int lcp(int a,int b)
{
a=rank[a];
b=rank[b];
if(a>b)swap(a,b);
a++;
int t=Log[b-a+1];
return min(best[t][a],best[t][b-(1<<t)+1]);
}
int rep[maxn];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n,p,T;
scanf("%d",&T);
while(T--)
{
scanf("%s",ss);
n=strlen(ss);
for(i=0;i<n;i++)str[i]=ss[i];
str[n]=0;
da(str,n+1,300);
calheight(str,n);
init(n);
long long ans=n;
for(i=1;i<n;i++)
ans+=lcp(0,i);
printf("%lld\n",ans);
}
return 0;
}
版权声明：本文为u012358934原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。