[SPOJ705]不同的子串

1709. [SPOJ705]不同的子串

★★   输入文件：subst1.in   输出文件：subst1.out   简单对比
时间限制：1 s   内存限制：256 MB

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

ABABA

【样例输出】

9

【来源】

SPOJ 705 New Distinct Substrings

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,maxx,c[N],sa[N],tsa[N],rank[N],trank[N],h[N];
char s[N];long long ans;
void DA(){
    int p;maxx=256;
    memset(c,0,sizeof c);
    for(int i=1;i<=n;i++) c[rank[i]=s[i]]++;
    for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[rank[i]]--]=i;
    trank[sa[1]]=p=1;
    for(int i=2;i<=n;i++){
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;
    }
    for(int i=1;i<=n;i++) rank[i]=trank[i];
    for(int k=1;p<n;k<<=1,maxx=p){
        p=0;
        for(int i=n-k+1;i<=n;i++) tsa[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;
        memset(c,0,sizeof c);
        for(int i=1;i<=n;i++) trank[i]=rank[tsa[i]];
        for(int i=1;i<=n;i++) c[trank[i]]++;
        for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i];
        trank[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
            if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++;
            trank[sa[i]]=p;
        }
        for(int i=1;i<=n;i++) rank[i]=trank[i];
    }
    for(int i=1,k=0;i<=n;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        h[rank[i]]=k;if(k>0) k--;
    }
}
int main(){
    freopen("subst1.in","r",stdin);
    freopen("subst1.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);
    DA();
    int ans=0;
    for(int i=1;i<=n;i++) ans+=(n-sa[i]+1-h[i]);
    printf("%d
",ans);
    return 0;
}