POJ1743 Musical Theme [后缀数组+分组/并查集]

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=2e4+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
    return x*f;
}
int n,m,k;
int s[N];
int sa[N],c[N],t1[N],t2[N],height[N],rnk[N];

void getHeight(){
    int k=0;
    for(int i=1;i<=n;i++) rnk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        if(k) k--;
        if(rnk[i]==1) continue;
        int j=sa[rnk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
        height[rnk[i]]=k;
    }
}
inline bool cmp(int *r,int a,int b,int j){
    return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
}
void getSA(){ 
    m=200;
    int *r=t1,*k=t2;
    for(int i=0;i<=m;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[r[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[r[i]]--]=i;

    for(int j=1;j<=n;j<<=1){
        int p=0;
        for(int i=n-j+1;i<=n;i++) k[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;

        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[r[k[i]]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i];

        swap(r,k);p=0;r[sa[1]]=++p;
        for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p;
        if(p>=n) break;m=p;
    }
}

struct edge{
    int v,ne;
}e[N];
int h[N],cnt;
inline void ins(int u,int v){
    cnt++;
    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
}
int fa[N],mn[N],mx[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unn(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){
        fa[x]=y;
        mn[y]=min(mn[y],mn[x]);
        mx[y]=max(mx[y],mx[x]);
    }
}
void solve(){
    cnt=0;memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        fa[i]=i,mn[i]=mx[i]=sa[i];
        ins(height[i],i);
    }
    for(int L=n-1;L>=4;L--){
        for(int i=h[L];i;i=e[i].ne) unn(e[i].v,e[i].v-1);
        if(h[L]){
            int x=find(e[h[L]].v);
            if(mx[x]-mn[x]>L) {printf("%d\n",L+1);return;} 
        }
    }
    puts("0");
}
int main(){
    freopen("in","r",stdin);
    while((n=read())){
        n--;
        int last=read(),x;
        for(int i=1;i<=n;i++){
            x=read();
            s[i]=x-last+100;
            last=x;
        }
        getSA();
        getHeight();
        solve();
    }
}