poj 1743 Musical Theme //后缀数组+二分

题目

题意

求能选出的两个字符串 $S$和 $T$，满足(1.不重叠，2.长度大于5且相等，3.所有的 $S[i]-T[i]$都相等)， $|S|$的最大值（不存在这样两个字符串，输出0。

思路

考虑相邻两项上做差得到新的数列，在此数列上跑SA。
二分答案，那么连续的 $height[i]$且 $height[i]>=mid$的一段里面判断 $sa[i]$的最大最小值是否差大于mid。
板子有问题，有地方会越界
补徐州camp

#include  <map>
#include  <set>
#include  <cmath>
#include  <queue>
#include  <cstdio>
#include  <vector>
#include  <climits>
#include  <cstring>
#include  <cstdlib>
#include  <iostream>
#include  <algorithm>
using namespace std;
#define FI first
#define SE second
#define LL long long
#define MP make_pair
#define PII pair<int,int>
#define SZ(a) (int)a.size()
const double pai = acos(-1);
const double eps = 1e-10;
const LL mod = 1e9+7;
const int MXN = 2e5+1;
/****************************************************************************/
int s[MXN];
int sua[MXN],t1[MXN],t2[MXN],c[MXN],rk[MXN],height[MXN];
void SABuild(int n,int m){ //[0,n)
    int *x=t1,*y=t2;
    for(int i=0;i<m;i++) c[i]=0;
    for(int i=0;i<n;i++) c[ x[i]=s[i] ]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sua[ --c[x[i]] ]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sua[i]>=k) y[p++]=sua[i]-k;
        for(int i=0;i<m;i++) c[i]=0;
        for(int i=0;i<n;i++) c[ x[y[i]] ]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sua[ --c[x[y[i]]] ]=y[i];
        swap(x,y);
        p=1;x[sua[0]]=0;
        for(int i=1;i<n;i++)
            x[sua[i]]=(y[sua[i-1]]==y[sua[i]]&&sua[i-1]+k<n&&sua[i]+k<n&&y[sua[i-1]+k]==y[sua[i]+k])?p-1:p++;
        if(p>=n) break;
        m=p;
    }
}
void heightGet(int n){
    int k=0;
    for(int i=0;i<n;i++) rk[sua[i]]=i;
    for(int i=0;i<n;i++){
        if(rk[i]==0) {height[rk[i]]=0;continue;}
        if(k) k--;
        int j=sua[rk[i]-1];
        while(j+k<n&&i+k<n&&s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;
    }
    for(int i=n;i>=1;i--)
        rk[i]=rk[i-1]+1,height[i]=height[i-1],sua[i]=sua[i-1]+1; //向前移一位
    rk[0]=height[0]=sua[0]=-1;

}
/****************************************************************************/
int sa[MXN];
int b[MXN];
bool check(int mid,int n){
    for(int i=2;i<=n;i++){
        if(height[i]>=mid) b[i]=1;
        else b[i]=0;
    }
    b[n+1]=0;
    for(int i=2;i<=n;i++){
        if(b[i]){
            int j;
            int mi=sua[i-1],mx=sua[i-1];
            for(j=i;j<=n+1;j++){
                if(b[j]==0) {j--;break;}
                mi=min(sua[j],mi),mx=max(sua[j],mx);
            }
            if(mx-mi>=mid) return 1;
            i=j;
        }
    }
    return 0;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        for(int i=0;i<n;i++) scanf("%d",&sa[i]);
        for(int i=0;i<n-1;i++) s[i]=sa[i+1]-sa[i]+100;
        SABuild(n-1,200);
        heightGet(n-1);
        int l=4,r=n-1,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid,n-1)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        cout<<ans+1<<'\n';
    }
    return 0;
}