SPOJ- Distinct Substrings(后缀数组&后缀自动机)

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.

题解：

本题题意就是给你一个字符串，让你找它有多少不同的子串；

其实就是SAM的板题，只要求每一个状态点的longest[i]-longest[fa[i]]的和就行了。

但由于是后缀数组专题，还是用后缀数组写：

参考代码：

后缀自动机：

#include<bits/stdc++.h>

using namespace std;

#define PI acos(-1.0)

#define mkp make_pair

#define pii pair<int,int>

#define fi first

#define se second

#define pb push_back

typedef long long ll;

const int INF=0x3f3f3f3f;

const int maxn=1e5+;

char s[maxn];

struct SAM{

    ll ans;

    int fa[maxn<<],l[maxn<<],nxt[maxn<<][],last,cnt;

    void Init()

    {

        memset(nxt[],,sizeof(nxt[]));

        last=cnt=; ans=;

        fa[]=;l[]=;

    }

    int NewNode()

    {

        ++cnt;

        memset(nxt[cnt],,sizeof(nxt[cnt]));

        fa[cnt]=l[cnt]=;

        return cnt;

    }

    void Add(int c)

    {

        int p=last,np=NewNode();

        last=np;l[np]=l[p]+;

        while(p&&!nxt[p][c]) nxt[p][c]=np,p=fa[p];

        if(!p) fa[np]=;

        else

        {

            int q=nxt[p][c];

            if(l[q]==l[p]+) fa[np]=q;

            else

            {

                int nq=NewNode();

                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));

                fa[nq]=fa[q];

                l[nq]=l[p]+;

                fa[q]=fa[np]=nq;

                while(nxt[p][c]==q) nxt[p][c]=nq,p=fa[p];

            }

        }

        ans+=(l[last]-l[fa[last]])*1ll;

    }

    void Query()

    {

        Init();

        for(int i=,len=strlen(s);i<len;++i) Add(s[i]-'A');

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

    }

} sam;

int main()

{

    int N;

    scanf("%d",&N);

    while(N--)

    {

        sam.Init();

        scanf("%s",s);

        sam.Query();

    }

    return ;

}

后缀数组：

#include<iostream>

#include<cstdio>

#include<cstring>

#define rint register int

#define ini inline int

#define maxn 1000050

using namespace std;

char str[maxn];

int y[maxn<<],x[maxn<<],c[maxn];

int sa[maxn],rk[maxn],height[maxn];

int n,m,s[maxn];

inline void get_SA()

{

    for(int i=;i<=m;++i) c[i]=;

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

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

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

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

    {

        int num=;

        for(int i=n-k+;i<=n;++i) y[++num]=i;

        for(int i=;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;

        for(int i=;i<=m;++i) c[i]=;

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

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

        for(int i=n;i>=;--i) sa[c[x[y[i]]]--]=y[i],y[i]=;

        swap(x,y);

        x[sa[]]=;

        num=;

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

            x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k])?num:++num;

        if(num==n) break;

        m=num;

    }

}

inline void get_height()

{

    int k=;

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

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

    {

        if(rk[i]==) continue;//第一名height为0

        if(k) --k;//h[i]>=h[i-1]-1;

        rint j=sa[rk[i]-];

        while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) ++k;

        height[rk[i]]=k;//h[i]=height[rk[i]];

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",str+);

        n=strlen(str+);m=;

        for(int i=;i<=n;++i) s[i]=str[i]-'A'+;

        get_SA();

        get_height();

        //for(int i=1;i<=n;++i) cout<<sa[i]<<" "<<height[i]<<endl;

        int ans=;

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

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

    }

    return ;

}

巴特西

SPOJ- Distinct Substrings(后缀数组&后缀自动机)

Input

Output

Example

最新文章

热门文章