SPOJ - Distinct Substrings，求不同的字串个数！

DISUBSTR - Distinct Substrings

题意：给你一个长度最多1000的字符串，求不相同的字串的个数。

思路：一个长度为n的字符串最多有(n+1)*n/2个，而height数组已经将所有的重复的都计算出来了，直接减去就行。需要注意的是在字符串的最后面加个0，不参与Rank排名，这样得到的height数组直接从1到n。

char s[N];

int sa[N],Rank[N],height[N],c[N],t[N],t1[N],n,m;

void build(int n)

{

    int i,*x=t,*y=t1;

    memset(c,0,sizeof(c));

    for(i=0; i<n; i++) c[x[i]=s[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(int k=1; k<=n; k<<=1)

    {

        int 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;

        memset(c,0,sizeof(c));

        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-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;

        if(p>=n) break;

        m=p;

    }

}

void get_height(int n)//n不保存最后的0

{

    int i,j,k=0;

    for(i=1; i<=n; i++)  Rank[sa[i]]=i;

    for(i=0; i<n; i++)

    {

        if(k) k--;

        j=sa[Rank[i]-1];

        while(s[i+k]==s[j+k])  k++;

        height[Rank[i]]=k;

    }

}

void show()

{

    puts("");

    for(int i=0;i<=n;i++) printf("%d ",i);

    puts("");

    for(int i=0;i<=n;i++) printf("%c ",s[i]);

    printf("\nsa:\n");

    for(int i=0;i<=n;i++) printf("%d ",sa[i]);

    printf("\nRank:\n");

    for(int i=0;i<=n;i++) printf("%d ",Rank[i]);

    printf("\nHight:\n");

    for(int i=0;i<=n;i++) printf("%d ",height[i]);

    puts("");

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",s);

        n=strlen(s);

        s[n]=0,m=125;

        build(n+1);

        get_height(n);

//        show();

        int ans=(n+1)*n/2;

        for(int i=1;i<=n;i++) ans-=height[i];

        printf("%d\n",ans);

    }

    return 0;

}

可以试着show()函数看看规律。