【SPOJ – SUBST1】New Distinct Substrings 后缀数组

New Distinct Substrings

题意

给出T个字符串，问每个字符串有多少个不同的子串。

思路

字符串所有子串，可以看做由所有后缀的前缀组成。

按照后缀排序，遍历后缀，每次新增的前缀就是除了与上一个后缀的所有公共前缀之外的前缀。

答案就是用总数-重复的即\(\frac{n(n+1)}{2}-\sum_{i=1}^{n}height[i]\)

代码

// #include <bits/stdc++.h>

#include <stdio.h>

#include <algorithm>

#include <string.h>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int inf = 0x3f3f3f3f;

int sa[N],cnt[N],pos[N],rk[N],oldrk[N],ht[N],n,m;

char str[N];

bool cmp(int a,int b,int k)

{

    return oldrk[a]==oldrk[b]&&oldrk[a+k]==oldrk[b+k];

}

void getsa()

{

    memset(cnt,0,sizeof(cnt));

    m=122;

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

        ++cnt[rk[i]=str[i]];

    for(int i=1; i<=m; i++)

        cnt[i]+=cnt[i-1];

    for(int i=n; i; i--)

        sa[cnt[rk[i]]--]=i;

    for(int k=1; k<=n; k<<=1)

    {

        int num=0;

        for(int i=n-k+1; i<=n; i++)

            pos[++num]=i;

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

        {

            if(sa[i]>k)

                pos[++num]=sa[i]-k;

        }

        memset(cnt,0,sizeof(cnt));

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

            ++cnt[rk[i]];

        for(int i=1; i<=m; i++)

            cnt[i]+=cnt[i-1];

        for(int i=n; i; i--)

            sa[cnt[rk[pos[i]]]--]=pos[i];

        memcpy(oldrk,rk,sizeof(rk));

        num=0;

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

            rk[sa[i]]=cmp(sa[i],sa[i-1],k)?num:++num;

        if(num==n)

            break;

        m=num;

    }

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

        rk[sa[i]]=i;

    int k=0;

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

    {

        if(k)

            --k;

        while(str[i+k]==str[sa[rk[i]-1]+k])

            ++k;

        ht[rk[i]]=k;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",str+1);

        n=strlen(str+1);

        getsa();

        ll sum=1LL*(n+1)*n/2;

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

            sum-=ht[i];

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

    }

    return 0;

}

巴特西

【SPOJ – SUBST1】New Distinct Substrings 后缀数组

New Distinct Substrings

题意

思路

代码

最新文章

热门文章