POJ 3693 Maximum repetition substring（字尾數組）

題意：

求重複次數最多的連續子串。

題解：

這是網上論文寫的，我跟着這個學習的，看這個應該比我講的好多了= =

AC代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define rint register int
const int MAXN = 1e5+10;
int rk[MAXN],y[MAXN],c[MAXN];
int sa[MAXN],h[MAXN];
char s[MAXN];
int dp[MAXN][20],Log[MAXN];
void pre(){
    Log[1]=0,Log[2]=1;
    for(rint i=3;i<=MAXN-10;i++)
        Log[i]=Log[i/2]+1;
}
void init(){
    memset(dp,0,sizeof(dp));
    memset(rk,0,sizeof(rk));
    memset(y,0,sizeof(y));
    memset(c,0,sizeof(c));
    memset(sa,0,sizeof(sa));
    memset(h,0,sizeof(h));
}
void SA(int n,int m){
    for(rint i=1;i<=n;i++) rk[i]=s[i],++c[rk[i]];
    for(rint i=1;i<=m;i++) c[i]+=c[i-1];
    for(rint i=1;i<=n;i++) sa[c[rk[i]]--]=i;
    for(rint k=1;k<=n;k<<=1){
        int num = 0;
        for(rint i=n-k+1;i<=n;i++) y[++num]=i;
        for(rint i=1;i<=n;i++)
            if(sa[i]>k)
                y[++num]=sa[i]-k;
        for(rint i=1;i<=m;i++) c[i]=0;
        for(rint i=1;i<=n;i++) ++c[rk[i]];
        for(rint i=1;i<=m;i++) c[i]+=c[i-1];
        for(rint i=n;i>=1;i--)
            sa[c[rk[y[i]]]--] = y[i];
        swap(rk,y);
        rk[sa[1]] = num = 1;
        for(rint i=2;i<=n;i++)
            rk[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? num : ++num);
        if(num == n) break;
        m = num;
    }
}
void H(int n){
    int k = 0;
    for(rint i=1;i<=n;i++){
        if(k) --k;
        int j=sa[rk[i]-1];
        while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) ++k;
        h[rk[i]]=k;
    }
}
void RMQ_INIT(int n){
    for(rint i=1;i<=n;i++) dp[i][0]=h[i];
    for(rint j=1;j<=Log[n];j++)
        for(rint i=1;i+(1<<j)-1<=n;i++)
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
int RMQ(int l,int r){
    if(l>r) swap(l,r);
    l++;
    int k = Log[r-l+1];
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(){
    int cas=0;
    pre();
    while(~scanf("%s",s+1)){
        if(strcmp(s+1,"#")==0) return 0;
        init();
        int n = strlen(s+1),m = 'z';
        SA(n,m);
        H(n);
        RMQ_INIT(n);
        int ans = 1,res = 1,now = sa[1];
        for(rint len=1;len<=n;len++){
            for(rint pos=0;pos+len<n;pos+=len){
                if(s[pos]!=s[pos+len]) continue;
                int LCP = RMQ(rk[pos],rk[pos+len]);
                if(LCP/len+1>ans || (LCP/len+1==ans && rk[pos]<rk[now])){
                    ans = LCP/len+1;//重複次數
                    now = pos;//位置
                    res = ans*len;//總的子串長度
                }
                int k = 1;
                while(k<len && k<=pos && s[pos-k]==s[pos+len-k]){
                    LCP++;
                    if(LCP/len+1>ans || (LCP/len+1==ans && rk[pos-k]<rk[now])){
                        ans = LCP/len+1;
                        now = pos-k;
                        res = ans*len;
                    }
                    k++;
                }
            }
        }
        printf("Case %d: ",++cas);
        for(rint i=0;i<res;i++) printf("%c",s[now+i]);
        printf("\n");
    }
}