New Distinct Substrings – SPOJ SUBST1 – 后缀数组

来源: New Distinct Substrings – SPOJ SUBST1 – Virtual Judge

题目大意:给定一个字符串,我们需要找到其不同子串的总数。
后缀数组height数组求相邻两串间的公共前缀(多加的)
题解:https://blog.csdn.net/bbbbswbq/article/details/78783573
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;

long long n;
int height[maxn],rrank[maxn],cnta[maxn],cntb[maxn],sa[maxn],a[maxn],b[maxn],tsa[maxn];
char ch[maxn];

void solve()
{
    memset(cnta,0,sizeof(cnta));
    for(int i=1;i<=n;i++)
        cnta[ch[i-1]]++;
    for(int i=1;i<256;i++)
        cnta[i]+=cnta[i-1];
    for(int i=n;i>0;i--)
        sa[cnta[ch[i-1]]--]=i;
    rrank[sa[1]]=1;
    for(int i=2;i<=n;i++)
    {
        rrank[sa[i]]=rrank[sa[i-1]];
        if(ch[sa[i]-1]!=ch[sa[i-1]-1])
            rrank[sa[i]]++;
    }
    for(int l=1;rrank[sa[n]]<n;l<<=1)
    {
        memset(cnta,0,sizeof(cnta));
        memset(cntb,0,sizeof(cntb));
        for(int i=1;i<=n;i++)
        {
            cnta[a[i]=rrank[i]]++;
            cntb[b[i]=(i+l<=n)?rrank[i+l]:0]++;
        }
        for(int i=1;i<=n;i++)cntb[i]+=cntb[i-1];
        for(int i=n;i>0;i--)tsa[cntb[b[i]]--]=i;
        for(int i=1;i<=n;i++)cnta[i]+=cnta[i-1];
        for(int i=n;i>0;i--)sa[cnta[a[tsa[i]]]--]=tsa[i];
        rrank[sa[1]]=1;
        for(int i=2;i<=n;i++)
        {
            rrank[sa[i]]=rrank[sa[i-1]];
            if(a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]])
                rrank[sa[i]]++;
        }
    }
    for(int i=1,j=0;i<=n;i++)
    {
        if(j)j--;
        while(ch[i+j-1]==ch[sa[rrank[i]-1]+j-1])j++;
        height[rrank[i]]=j;
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>ch;
        n=strlen(ch);
        if(n==1)
        {
            cout<<"1"<<endl;
            continue;
        }
        solve();
        long long ans=(n+1)*n/2;
        for(int i=2;i<=n;i++)
            ans-=height[i];
        cout<<ans<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注