codeforces 427D Match & Catch（后缀数组，字符串）

题目

参考：http://blog.csdn.net/xiefubao/article/details/24934617

//如果一个长度len合法的话：则一定存在这个样的sa[i]排名。

//sa[i]与s[i+1]的公共前缀长度大于等于len，

//且sa[i]与[i-1]的公共前缀长度小于len，

//同时 sa[i+1]与[i+2]的公共前缀长度小于len，

//同时保证sa[i]与sa[i+1]在两个串中。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define maxn 1000001

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];

int cmp(int *r,int a,int b,int l)

{return r[a]==r[b]&&r[a+l]==r[b+l];}

void da(int *r,int *sa,int n,int m){

     int i,j,p,*x=wa,*y=wb,*t;

     for(i=;i<m;i++) ws[i]=;

     for(i=;i<n;i++) ws[x[i]=r[i]]++;

     for(i=;i<m;i++) ws[i]+=ws[i-];

     for(i=n-;i>=;i--) sa[--ws[x[i]]]=i;

     for(j=,p=;p<n;j*=,m=p){

       for(p=,i=n-j;i<n;i++) y[p++]=i;

       for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

       for(i=;i<n;i++) wv[i]=x[y[i]];

       for(i=;i<m;i++) ws[i]=;

       for(i=;i<n;i++) ws[wv[i]]++;

       for(i=;i<m;i++) ws[i]+=ws[i-];

       for(i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];

       for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)

       x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;

     }

     return;

}

int rankk[maxn],height[maxn];

void calheight(int *r,int *sa,int n){

     int i,j,k=;

     for(i=;i<=n;i++) rankk[sa[i]]=i;

     for(i=;i<n;height[rankk[i++]]=k)

     for(k?k--:,j=sa[rankk[i]-];r[i+k]==r[j+k];k++);

     return;

}

char s[];

int len1,len2;

int r[],sa[];

//这是一个除去下标影响的好方法呀

int judge(int n,int k ){

    int a,b;a=b=;

    for(int i=;i<=n;i++){

        if(height[i]<k){

            if(a==&&b==)return ;

            a=,b=;

        }

        if(sa[i]>=&&sa[i]<len1)a++;

        if(sa[i]>len1&&sa[i]<len2)b++;

    }

    return ;

}

int main(){

    scanf("%s",s);

    len1=strlen(s);

    s[len1]=;

    scanf("%s",s+len1+);

    len2=strlen(s);

    for(int i=;i<len2;i++)r[i]=s[i];

    r[len2]=;

    da(r,sa,len2+,);

    calheight(r,sa,len2);

    int ans=-;

    for(int i=;i<=len1;i++){//枚举长度

        if(judge(len2+,i)){

            ans=i;break;

        }

    }

    printf("%d\n",ans);

    return ;

}