SPOJ:REPEATS

http://www.spoj.com/problems/REPEATS/

　　求重复次数最多的连续重复子串。

　　论文题。枚举子串长度L，重复一次是肯定的，我们考虑至少重复两次的情况。那么在1，L+1,2L+1...kL+1这些位置一定会覆盖至少连续的两个。于是我们枚举连续的两个位置，向前向后匹配，匹配总长/L+1即为重复次数。

#include<bits/stdc++.h>
using namespace std;
const int maxn=50015;
int n,len;char s[maxn<<1];
struct Tsuffix_array{
    static const int maxn=::maxn<<1;
    int sum[maxn],sa[maxn],rank[maxn],tsa[maxn],trank[maxn];
    bool cmp(int i,int j,int l){
        if (i+l>len||j+l>len) return 0;
        return rank[i]==rank[j]&&rank[i+l]==rank[j+l];
    }
    void suffix_sort(){
        int m=255,p,i,j;
        for (i=0;i<=m;++i) sum[i]=0;
        for (i=1;i<=len;++i) ++sum[rank[i]=s[i]];
        for (i=1;i<=m;++i) sum[i]+=sum[i-1];
        for (i=len;i>=1;--i) sa[sum[rank[i]]--]=i;
        for (p=0,j=1;p<len;j<<=1,m=p){
            for (p=0,i=len-j+1;i<=len;++i) tsa[++p]=i;
            for (i=1;i<=len;++i) if (sa[i]>j) tsa[++p]=sa[i]-j;
            for (i=0;i<=m;++i) sum[i]=0;
            for (i=1;i<=len;++i) ++sum[rank[tsa[i]]];
            for (i=1;i<=m;++i) sum[i]+=sum[i-1];
            for (i=len;i>=1;--i) sa[sum[rank[tsa[i]]]--]=tsa[i];
            for (p=trank[sa[1]]=1,i=2;i<=len;++i) trank[sa[i]]=cmp(sa[i],sa[i-1],j)?p:++p;
            memcpy(rank,trank,sizeof(int)*(len+1));
        }
    }
    static const int maxk=20;
    int height[maxn],fmn[maxk][maxn];
    void get_height(){
        for (int h=0,i=1;i<=len;++i){
            if (rank[i]==1) continue;
            for (h?--h:0;s[i+h]==s[sa[rank[i]-1]+h];++h);
            height[rank[i]]=h;
        }
        for (int i=2;i<=len;++i) fmn[0][i]=height[i];
        for (int k=1;k<maxk;++k)
            for (int i=1<<k;i<=len;++i)
                fmn[k][i]=min(fmn[k-1][i],fmn[k-1][i-(1<<(k-1))]);
    }
    int LCP(int x,int y){
        if (x>y) swap(x,y);
        int k=log2(y-(++x)+1);
        return min(fmn[k][y],fmn[k][x+(1<<k)-1]);
    }
    int check(int l){
        int res=0;
        for (int i=1,j=l+1;j<=n;i=j,j=i+l){
            int Rmatch=LCP(rank[i],rank[j]);
            int Lmatch=LCP(rank[n+1+(n-i+1)],rank[n+1+(n-j+1)]);
            res=max(res,(Lmatch+Rmatch-1)/l+1);
        }
        return res;
    }
}SA;
void init(){
    scanf("%d",&n);s[n+1]=1;len=(n<<1)+1;s[len+1]=0;
    for (int i=1;i<=n;++i){char c[2];scanf("%s",c);s[i]=c[0];}
    for (int i=1;i<=n;++i) s[n+1+(n-i+1)]=s[i];
}
void work(){
    SA.suffix_sort();
    SA.get_height();
    int res=1;
    for (int i=1;i<=n/2;++i) res=max(res,SA.check(i));
    printf("%d
",res);
}
int main(){
    int cases;scanf("%d",&cases);
    while (cases--){init();work();}
    return 0;
}