Repeats – SPOJ REPEATS – 后缀数组

来源: Repeats – SPOJ REPEATS – Virtual Judge

题目大意:求重复次数最多的连续重复子串
详见:罗穗骞论文第21页
代码

#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 minnum[maxn][16];

void rmq()
{
    int m=(int)(log(n*1.0)/log(2.0));
    for(int i=1;i<=n;i++)
    {
        minnum[i][0]=height[i];
    }
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            minnum[i][j]=min(minnum[i][j-1],minnum[i+(1<<(j-1))][j-1]);
        }
    }
}

int askmin(int a,int b)
{
    int k=(int)(log(b-a+1.0)/log(2.0));
    return min(minnum[a][k],minnum[b-(1<<k)+1][k]);
}

int calprefix(int a,int b)
{
    a=rrank[a],b=rrank[b];
    if(a>b)
        swap(a,b);
    return askmin(a+1,b);
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>ch[i];
        }
        solve();
        rmq();
        int k;
        long long maxx=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j+i<n;j+=i)
            {
                ans=calprefix(j,j+i);
                k=j-(i-ans%i);
                ans=ans/i+1;
                if(k>=0&&calprefix(k,k+i)>=i)
                    ans++;
                maxx=max(maxx,ans);
            }
        }
        cout<<maxx<<endl;
    }
    return 0;
}

发表评论

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