cogs1713 [POJ2774]很长的信息

---

原题链接

---

题解

把两串拼成A+'%'+B+'$'。跑后缀数组然后相邻两点i,i+1不在同一串里就用ht[i]更新答案。

好裸。。。

---

Code

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#include<cstring>

#define Fname "lcs"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

il int gi(){

    rg int x=0;rg char ch=getchar();

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x;

}

const int maxn=1200010;

char A[maxn],B[maxn];

int a,b;

int n,s[maxn],m;

int sa[maxn],rk[maxn],tmp[maxn],buc[maxn],ht[maxn];

il vd Qsort(){

    rep(i,0,m)buc[i]=0;

    rep(i,1,n)buc[rk[tmp[i]]]++;

    rep(i,1,m)buc[i]+=buc[i-1];

    drep(i,n,1)sa[buc[rk[tmp[i]]]--]=tmp[i];

}

il bool cmp(int*h,int a,int b,int l){return h[a]==h[b]&&h[a+l]==h[b+l];}

il vd solve(){

    m=127;

    rep(i,1,n)rk[i]=s[i],tmp[i]=i;

    Qsort();

    int p=0;

    for(rg int l=1;p<n;l<<=1){

	p=0;

	rep(i,n-l+1,n)tmp[++p]=i;

	rep(i,1,n)if(sa[i]>l)tmp[++p]=sa[i]-l;

	Qsort();

	rep(i,1,n)tmp[i]=rk[i];

	p=rk[sa[1]]=1;

	rep(i,2,n)

	    if(cmp(tmp,sa[i],sa[i-1],l))rk[sa[i]]=p;

	    else rk[sa[i]]=++p;

	m=p;

    }

    p=0;

    rep(i,1,n)sa[rk[i]]=i;

    rep(i,1,n){

	if(p)--p;

	if(rk[i]==n)continue;

	while(s[i+p]==s[sa[rk[i]+1]+p])++p;

	ht[rk[i]]=p;

    }

}

il bool check(int&x,int&y){

    if(x<=a&&y>a+1)return 1;

    if(y<=a&&x>a+1)return 1;

    return 0;

}

int main(){

    freopen(Fname".in","r",stdin);

    freopen(Fname".out","w",stdout);

    scanf("%s%s",A+1,B+1);

    a=strlen(A+1),b=strlen(B+1);

    rep(i,1,a)s[++n]=A[i];

    s[++n]='%';

    rep(i,1,b)s[++n]=B[i];

    s[n+1]='$';

    solve();

    int ans=0;

    rep(i,1,n-1)if(check(sa[i],sa[i+1]))ans=max(ans,ht[i]);

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

    return 0;

}