[SPOJ705]不同的子串

题目描述】

给定一个字符串，计算其不同的子串个数。

【输入格式】

一行一个仅包含大写字母的字符串，长度<=50000

【输出格式】

一行一个正整数，即不同的子串个数。

【样例输入】

ABABA

【样例输出】

题解：

显然后缀可以是一个子串，然后后缀中可能包含多个子串。

我们考虑不重复统计，容易发现一个后缀的贡献为L-high[i]+1

因为high[i]之前的显然可以在后面的串中被统计到，所以可以避免重复

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=50005;
 9 char s[N];int n,k,rk[N],sa[N],tmp[N],high[N];
10 bool comp(int i,int j){
11     if(rk[i]!=rk[j])return rk[i]<rk[j];
12     int ri=i+k<=n?rk[i+k]:-1;
13     int rj=j+k<=n?rk[j+k]:-1;
14     return ri<rj;
15 }
16 void Getsa(){
17     for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
18     for(k=1;k<=n;k<<=1){
19         sort(sa+1,sa+n+1,comp);
20         for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+comp(sa[i-1],sa[i]);
21         for(int i=1;i<=n;i++)rk[i]=tmp[i];
22     }
23 }
24 void Gethight(){
25     int j,h=0;
26     for(int i=1;i<=n;i++){
27         j=sa[rk[i]-1];
28         if(h)h--;
29         for(;j+h<=n && i+h<=n;h++)if(s[i+h]!=s[j+h])break;
30         high[rk[i]-1]=h;
31     }
32 }
33 void Getanswer(){
34     long long ans=0;
35     for(int i=1;i<=n;i++){
36         if(high[i]==n-sa[i]+1)continue;
37         ans+=n-sa[i]+1-high[i];
38     }
39     printf("%lld
",ans);
40 }
41 int main()
42 {
43     freopen("subst1.in","r",stdin);
44     freopen("subst1.out","w",stdout);
45     scanf("%s",s+1);
46     n=strlen(s+1);
47     Getsa();Gethight();Getanswer();
48     return 0;
49 }