spoj 접미사 배열

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=115232#problem/B
문자열 의 모든 중복 되 지 않 는 하위 문자열 을 보 여 주 십시오. 겹 칠 수 있 습 니 다.
모든 접미사 의 모든 접 두 사 는 모든 문자열 을 포함 합 니 다. 중복 문자열 의 개 수 를 줄 이 는 것 은 모든 height [] 입 니 다.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=100010;

int wa[maxn], wb[maxn], wv[maxn], ws1[maxn],sa[maxn];
int cmp(int *r, int a, int b, int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
    int i, j, p, *x = wa,*y = wb;
    //                   ：                      
    for(i = 0; i<m; i++) ws1[i]=0; //             
    for(i = 0; i<n; i++) ws1[x[i]=r[i]]++; //          
    for(i = 1; i<m; i++) ws1[i]+=ws1[i-1]; //       ，                      
    for(i = n-1; i>=0; i--) sa[--ws1[x[i]]]=i; //        ，sa[x] = i，  i     x 
    // wa[x[i]]     0-x[i]           ，                    ，   0  
    //                          ，    wa[x[i]]       ，         
    //     ，                 ，                          


    //                         ，      
    //             ，                   
    for(j = 1, p = 1; p<n; j*=2, m=p)
    {
        for(p = 0, i = n-j; i<n; i++) y[p++]=i; //         i        ，  i  ，         
        //          j  ，  i                ，           ，          
        for(i = 0; i<n; i++)
            if(sa[i]>=j) y[p++]=sa[i]-j; // sa[i]-j               sa[i]    ，sa[i]<j              
        for(i = 0; i<n; i++) wv[i]=x[y[i]]; //             
        for(i = 0; i<m; i++) ws1[i]=0;
        for(i = 0; i<n; i++) ws1[wv[i]]++;
        for(i = 1; i<m; i++) ws1[i]+=ws1[i-1];
        for(i = n-1; i>=0; i--) sa[--ws1[wv[i]]]=y[i]; //                    
        for(swap(x,y),p=1,x[sa[0]]=0,i=1; i<n; i++) //      sa           、    
            x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}

int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n) //    n        ，       0
{
    int i,j,k=0;
    for(i = 1; i<=n; i++) rank[sa[i]]=i; //            ，   0         0
    for(i = 0; i<n; height[rank[i++]]=k) //   i            i-1          k-1      
        for(k?k--:0, j=sa[rank[i]-1]; r[i+k] == r[j+k]; k++); //          ，              O(n) 
    return;
}


char s[maxn];
int ss[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        int n=strlen(s);
        for(int i=0;i<=n;i++) ss[i]=s[i];
        da(ss,sa,n+1,128);
        calheight(ss,sa,n);
        int ans=n*(n+1)/2;
        for(int i=2;i<=n;i++)ans-=height[i];
        printf("%d
",ans);
    }
    return 0;
}

705 는 기본적으로 똑 같 아 요. 범위 가 넓 어서 롱 롱 으로 바 뀌 었 어 요.

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