SPOJ SUBST1 后缀数组

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

题意：给定一个字符串，求不相同的子串个数。

思路：直接根据09年oi论文<<后缀数组——出来字符串的有力工具>>的解法。

此题和SPOJ DISUBSTR一样，至少数据范围变大了。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<cmath>

using namespace std;

typedef long long int LL;

const int MAXN =  + ;

int cmp(int *r, int a, int b, int l){

    return r[a] == r[b] && r[a + l] == r[b + l];

}

int wa[MAXN], wb[MAXN], wv[MAXN], WS[MAXN];

void da(int *r, int *sa, int n, int m){

    int i, j, p, *x = wa, *y = wb, *t;

    for (i = ; i<m; i++) WS[i] = ;

    for (i = ; i<n; i++) WS[x[i] = r[i]]++;

    for (i = ; i<m; i++) WS[i] += WS[i - ];

    for (i = n - ; i >= ; i--) sa[--WS[x[i]]] = i;

    for (j = , p = ; p<n; j *= , m = p)

    {

        for (p = , i = n - j; i<n; i++) y[p++] = i;

        for (i = ; i<n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;

        for (i = ; i<n; i++) wv[i] = x[y[i]];

        for (i = ; i<m; i++) WS[i] = ;

        for (i = ; i<n; i++) WS[wv[i]]++;

        for (i = ; i<m; i++) WS[i] += WS[i - ];

        for (i = n - ; i >= ; i--) sa[--WS[wv[i]]] = y[i];

        for (t = x, x = y, y = t, p = , x[sa[]] = , i = ; i<n; i++)

            x[sa[i]] = cmp(y, sa[i - ], sa[i], j) ? p -  : p++;

    }

    return;

}

int Rank[MAXN], height[MAXN], sa[MAXN];

void calheight(int *r, int *sa, int n){

    int i, j, k = ;

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

    for (i = ; i < n; height[Rank[i++]] = k)

        for (k ? k-- : , j = sa[Rank[i] - ]; r[i + k] == r[j + k]; k++);

    return;

}

void solve(int n){

    int ans = ;

    for (int i = ; i <= n; i++){

        ans += ((n - ) - sa[i] +  - height[i]);

    }

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

}

int t, len, r[MAXN];

char str[MAXN];

int main(){

    //#ifdef kirito

    //    freopen("in.txt","r",stdin);

    //    freopen("out.txt","w",stdout);

    //#endif

    //    int start = clock();

    scanf("%d", &t);

    while (t--){

        scanf("%s", str); len = strlen(str);

        for (int i = ; i <= len; i++){

            if (i == len){ r[i] = ; continue; }

            r[i] = (int)str[i];

        }

        da(r, sa, len + , );

        calheight(r, sa, len);

        solve(len);

    }

    //#ifdef LOCAL_TIME

    //    cout << "[Finished in " << clock() - start << " ms]" << endl;

    //#endif

    return ;

}