poj 2774求两个串的公共前缀 后缀数组

////  main.cpp//  后缀数组////  Created by liuzhe on 17/2/5.//  Copyright © 2017年 my_code. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>using namespace std;//poj 2774后缀数组求最长公共字串const int maxn = 200010;int wa[maxn],wb[maxn],wv[maxn],ww[maxn];int sa[maxn],lcp[maxn],rank[maxn],rank1[maxn];char str[maxn],str1[maxn];inline bool cmp(int *r,int a,int b,int len){    return r[a]==r[b]&&r[a+len]==r[b+len];}void construct_sa(int n,int m){    int i,j,p,*x=wa,*y=wb,*t;    for(i=0;i<m;i++)        ww[i] = 0;    for(i=0;i<n;i++)        ww[x[i]=str[i]]++;    for(i=1;i<m;i++)        ww[i] += ww[i-1];    for(i=n-1;i>=0;i--)        sa[--ww[x[i]]] = i;    for(j=p=1;p<n;j<<=1,m=p)    {        for(p=0,i=n-j;i<n;i++)            y[p++] = i;        for(i=0;i<n;i++){            if(sa[i]>=j)                y[p++] = sa[i]-j;        }        for(i=0;i<m;i++)            ww[i] = 0;        for(i=0;i<n;i++)            ww[wv[i]=x[y[i]]] ++;        for(i=1;i<m;i++)            ww[i]+=ww[i-1];        for(i=n-1;i>=0;i--)            sa[--ww[wv[i]]] = y[i];        for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;    }}void construct_lcp(int n){    for(int i=0;i<=n;i++)        rank1[sa[i]] = i;    int h = 0;    lcp[0] = 0;    for(int i=0;i<n;i++)    {        int j = sa[rank1[i]-1];        if(h>0)            h--;        for(;j+h<n && i+h<n;h++)            if(str[i+h]!=str[j+h])                break;        lcp[rank1[i]-1] = h;    }}int main(){    gets(str);    gets(str1);    int len1=strlen(str),len2=strlen(str1);    str[len1] = '*';    for(int i=0;i<len2;i++)        str[len1+1+i] = str1[i];    int n = len1 + len2 + 1;    construct_sa(n+1,300);    construct_lcp(n);    int ans = 0;    for(int i=0;i<n;i++)        if((sa[i]<len1)!=sa[i+1]<len1)            ans = max(ans,lcp[i]);    PRintf("%d/n",ans);    return 0;}