DISUBSTR - Distinct Substrings

2022-03-13 08:42:15

DISUBSTR - 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 <= 1000

Output

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

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

Explanation for the testcase with string ABABA:
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

分析：字符串中不同子串的个数；

　　　建立后缀数组对每一个后缀算贡献即可；

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define ld long double

#define pi acos(-1.0)

#define pii pair<int,int>

#define Lson L, mid, ls[rt]

#define Rson mid+1, R, rs[rt]

#define sys system("pause")

#define freopen freopen("in.txt","r",stdin)

const int maxn=1e3+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

inline ll read()

{

    ll x=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,k,t,cntA[maxn],cntB[maxn],sa[maxn],lev[maxn],height[maxn],A[maxn],B[maxn],tsa[maxn];

char ch[maxn];

void solve()

{

    for (int i = ; i < ; i ++) cntA[i] = ;

    for (int i = ; i <= n; i ++) cntA[ch[i]] ++;

    for (int i = ; i < ; i ++) cntA[i] += cntA[i - ];

    for (int i = n; i; i --) sa[cntA[ch[i]] --] = i;

    lev[sa[]] = ;

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

    {

        lev[sa[i]] = lev[sa[i - ]];

        if (ch[sa[i]] != ch[sa[i - ]]) lev[sa[i]] ++;

    }

    for (int l = ; lev[sa[n]] < n; l <<= )

    {

        for (int i = ; i <= n; i ++) cntA[i] = ;

        for (int i = ; i <= n; i ++) cntB[i] = ;

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

        {

            cntA[A[i] = lev[i]] ++;

            cntB[B[i] = (i + l <= n) ? lev[i + l] : ] ++;

        }

        for (int i = ; i <= n; i ++) cntB[i] += cntB[i - ];

        for (int i = n; i; i --) tsa[cntB[B[i]] --] = i;

        for (int i = ; i <= n; i ++) cntA[i] += cntA[i - ];

        for (int i = n; i; i --) sa[cntA[A[tsa[i]]] --] = tsa[i];

        lev[sa[]] = ;

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

        {

            lev[sa[i]] = lev[sa[i - ]];

            if (A[sa[i]] != A[sa[i - ]] || B[sa[i]] != B[sa[i - ]]) lev[sa[i]] ++;

        }

    }

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

    {

        if (j) j --;

        while (ch[i + j] == ch[sa[lev[i] - ] + j]) j ++;

        height[lev[i]] = j;

    }

}

int main()

{

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",ch+);

        n=strlen(ch+);

        solve();

        ll ans=;

        rep(i,,n)

        {

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

        }

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

    }

    //system("Pause");

    return ;

}

码农公寓