spoj705 后缀数组求不同子串的个数

http://www.spoj.com/problems/SUBST1/en/  题目链接

SUBST1 - New Distinct Substrings

no tags 

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

Output

For each test case output one number saying the number of distinct substrings.

Example

Input:
2
CCCCC
ABABA

Output:
5

9

题意:

求不同的子串的个数。

思路:

每一个子串都是某一个后缀的前缀。所以对于当前的后缀，他能够贡献的个数就是他的长度减去

rank[i]-1的那个的公共前缀长度。

 

/*
 * Author:  sweat123
 * Created Time:  2016/6/29 13:46:26
 * File Name: main.cpp
 */
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = 50010;
char s[MAXN];
int wa[MAXN],wb[MAXN],wc[MAXN],n,height[MAXN],r[MAXN],Rank[MAXN],sa[MAXN];
void da(int *r,int *sa,int n,int m){
    int *x = wa,*y = wb;
    for(int i = 0; i < m; i++)wc[i] = 0;
    for(int i = 0; i < n; i++)wc[x[i] = r[i]] ++;
    for(int i = 0; i < m; i++)wc[i] += wc[i-1];
    for(int i = n - 1; i >= 0; i--)sa[--wc[x[i]]] = i;
    for(int p = 1,k = 1; p < n; m = p,k <<= 1){
        p = 0;
        for(int i = n - k; i < n; i++)y[p++] = i;
        for(int i = 0; i < n; i++)if(sa[i] >= k)y[p++] = sa[i] - k;
        for(int i = 0; i < m; i++)wc[i] = 0;
        for(int i = 0; i < n; i++)wc[x[y[i]]] ++;
        for(int i = 0; i < m; i++)wc[i] += wc[i-1];
        for(int i = n - 1; i >= 0; i--)sa[--wc[x[y[i]]]] = y[i];
        swap(x,y);
        p = 1;
        x[sa[0]] = 0;
        for(int 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++;   
        }
    }   
}
void calheight(int *r,int *sa,int n){
    for(int i = 1; i <= n; i++)Rank[sa[i]] = i;
    int j,k;
    k = 0;
    for(int i = 0; i < n; height[Rank[i++]] = k){
        for(k?k--:0,j = sa[Rank[i]-1]; r[j+k] == r[i+k]; k++);
    }   
}
void solve(){
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int tp = height[i];
        int len = n - sa[i];
        ans += len - tp;
    }   
    printf("%d
",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s",s);
        n = strlen(s);
        for(int i = 0; i < n; i++){
            r[i] = s[i];
        }   
        r[n] = 0;
        da(r,sa,n+1,128);
        calheight(r,sa,n);
        solve();
    }
    return 0;
}