spoj-694-Distinct Substrings(后缀数组)

时间：2022-04-01 08:58:29

题意：

给定一个字符串,求不相同的子串的个数

分析：

每个子串一定是某个后缀的前缀,那么原问题等价于求所有后缀之间的不相同 的 前 缀 的 个 数 。

如 果 所 有 的 后 缀 按 照 suffix(sa[1]), suffix(sa[2]),suffix(sa[3]), ...... ,suffix(sa[n])的顺序计算,

不难发现,对于每一次新加进来的 后缀 suffix(sa[k]), 它将产生 n-sa[k] 个新 的前缀。

但 是其中有height[k]个是和前面的字符串的前缀是相同的。

所以 suffix(sa[k])将“贡献”出 n-sa[k]- height[k]个不同的子串。

累加后便是原问题的答案。这个做法的时间复杂度为 O(n)。

// File Name: 694.cpp

// Author: Zlbing

// Created Time: 2013年09月06日 星期五 13时34分31秒

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

//rank从0开始

//sa从1开始,因为最后一个字符(最小的)排在第0位

//height从2开始,因为表示的是sa[i-1]和sa[i]

const int MAXN=;

int rank[MAXN],sa[MAXN],X[MAXN],Y[MAXN],height[MAXN];

char s[MAXN];

int buc[MAXN];

void calheight(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]-] ; s[i+k] == s[j+k] ; k++);

}

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

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

}

void suffix(int n,int m = ) {

    int i , l , p , *x = X , *y = Y;

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

    for(i =  ; i < n ; i ++) buc[ x[i] = s[i]  ] ++;

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

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

    for(l = ,p =  ; p < n ; m = p , l *= ) {

        p = ;

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

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

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

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

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

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

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

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

    }

    calheight(n-);//后缀数组关键是求出height,所以求sa的时候顺便把rank和height求出来

}

int solve(int n)

{

    int ans=;

    ans+=n-sa[];

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

    {

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

    }

    return ans;

}

int main() {

    int cas;

    scanf("%d",&cas);

    while(cas--)

    {

        scanf("%s",s);

        int n=strlen(s);

        s[n]=;

        suffix(n+);

        int ans=solve(n);

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

    }

    return ;

}

相关文章