Musical Theme – POJ 1743 – 二分+后缀数组

来源: Musical Theme – POJ 1743 – Virtual Judge

解题思路:参照罗穗骞的后缀数组论文第18页
代码

#include <iostream>
#include <cstring>
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];
int 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<20005; 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 check(int k)
{
    int mx=-0x3f3f3f3f,mm=0x3f3f3f3f;
    for(int i=1; i<=n; i++)
    {
        if(height[i]>=k)
        {
            mm=min(mm,min(sa[i],sa[i-1]));
            mx=max(mx,max(sa[i],sa[i-1]));
            if(mx-mm>k)
                return 1;
        }
        else
        {
            mx=-0x3f3f3f3f;
            mm=0x3f3f3f3f;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        for(int i=0; i<n; i++)
        {
            cin>>ch[i];
        }
        n--;
        for(int i=0; i<n; i++)
        {
            ch[i]=ch[i+1]-ch[i]+88;
        }
        solve();
        int l=0,r=n/2;
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(check(mid))
                l=mid;
            else
                r=mid-1;
        }
        if(l>=4)
            cout<<l+1<<endl;
        else
            cout<<"0"<<endl;
    }
    return 0;
}

发表评论

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