POJ 3693 Maximum repetition substring (后缀数组+RMQ 求重复最多的连续子串)

给定一个字符串，求重复次数最多的连续重复子串。


先穷举长度L，然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的，所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次，记这个子字符串为S，那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远，记这个总长度为K，那么这里连续出现了K/L+1 次。最后看最大值是多少

难点主要在于向前匹配的过程，处理的时候不是真的向前匹配，而是把LCP长度向前拓展凑成循环长度的整数倍再求LCP

//10004K	329MS	C++	3962B
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1e5+1e3;

int t1[MAXN],t2[MAXN],c[MAXN];
bool cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int str[],int sa[],int rank[],int height[],int n,int m)
{
    n++;
    int i,j,p,*x=t1,*y=t2;
    for(i=0;i<m;i++) c[i]=0;
    for(i=0;i<n;i++) c[x[i]=str[i]]++;
    for(i=1;i<m;i++) c[i]+=c[i-1];
    for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        for(i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[y[i]]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0;i<=n;i++) rank[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k) k--;
        j=sa[rank[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rank[i]]=k;
    }
}
int rank[MAXN],height[MAXN];
int RMQ[MAXN];
int mm[MAXN];
int best[20][MAXN];
void initRMQ(int n)
{
    mm[0]=-1;
    for(int i=1;i<=n;i++)
        mm[i]=((i&(i-1))==0)? mm[i-1]+1:mm[i-1];
    for(int i=1;i<=n;i++) best[0][i]=i;
    for(int i=1;i<=mm[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            int a=best[i-1][j];
            int b=best[i-1][j+(1<<(i-1))];
            if(RMQ[a]<RMQ[b]) best[i][j]=a;
            else best[i][j]=b;
        }
}
int askRMQ(int a,int b)
{
    int t;
    t=mm[b-a+1];
    b-=(1<<t)-1;
    a=best[t][a];
    b=best[t][b];
    return RMQ[a]<RMQ[b] ? a:b;
}
int lcp(int a,int b)
{
    a=rank[a];
    b=rank[b];
    if(a>b) swap(a,b);
    return height[askRMQ(a+1,b)];
}

char str[MAXN];
int r[MAXN];
int sa[MAXN];


int cirl[MAXN];
int main()
{
    int cas=0;
    while(scanf("%s",str))
    {
        int len=strlen(str);
        if(len==1&&str[0]=='#') break;
        for(int i=0;i<len;i++) r[i]=str[i]-'a'+1;   //注意最小的字符的值必须比0大，因为da中默认0比任何字符小
        r[len]=0;
        da(r,sa,rank,height,len,30);
        for(int i=1;i<=len;i++) RMQ[i]=height[i];
        initRMQ(len);

        int maxn=-1,top=0;
        for(int l=1;l<len;l++)
            for(int p=0 ; p+l<len ; p+=l)
            {
                int t1= lcp(p,p+l);
                int tmp= t1/l+1;
                int k=p-(l-t1%l);
                if(k>=0&&t1%l)
                {
                    int t2 = lcp(k,k+l);
                    if(t2>t1) tmp++;
                }
                if(tmp>maxn)
                {
                    top=0;
                    cirl[top++]=l;
                    maxn=tmp;
                }
                else if(tmp==maxn)
                {
                    cirl[top++]=l;
                }
            }
        sort(cirl,cirl+top); //YY
        int st,ed=-1;
        for(int i=1;i<=len&&ed==-1;i++)
            for(int j=0;j<top;j++)
            {
                if(sa[i]+cirl[j]>len) continue;
                int a=sa[i],b=sa[i]+cirl[j];
                if(lcp(a,b)>=(maxn-1)*cirl[j])
                {
                    st=sa[i];
                    ed=st+cirl[j]*maxn;
                    break;
                }
            }
        str[ed]=0;
        printf("Case %d: %s\n",++cas,str+st);
    }
    return 0;
}

POJ 3693 Maximum repetition substring (后缀数组+RMQ 求重复最多的连续子串)

原文：http://blog.csdn.net/kalilili/article/details/44572643