題意：

求兩個(gè)串的最長(zhǎng)連續(xù)子串。

我的想法：

? ? ? 枚舉第二個(gè)串...在第一個(gè)串的后綴數(shù)組中二分查找.

? ? ? 復(fù)雜度NlogN。最壞情況N^2

題解：

（3）height 數(shù)組：定義height[i]=suffix(SA[i-1])和suffix(SA[i])的最長(zhǎng)公共前綴，也就是排名相鄰的兩個(gè)后綴的最長(zhǎng)公共前綴。

（4） h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后綴的最長(zhǎng)公共前綴。

（5）LCP(i,j)：對(duì)正整數(shù)i,j 定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均為1 至n 的整數(shù)。LCP(i,j)也就是后綴數(shù)組中第i 個(gè)和第j 個(gè)后綴的最長(zhǎng)公共前綴的長(zhǎng)度。其中，函數(shù)lcp(u,v)=max{i|u=v}，也就是從頭開始順次比較u 和v 的對(duì)應(yīng)字符，對(duì)應(yīng)字符持續(xù)相等的最大位置，稱為這兩個(gè)字符串的最長(zhǎng)公共前綴。

2.2?? 幾個(gè)性質(zhì)

（1）LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是說(shuō)，計(jì)算LCP(i,j)等同于詢問(wèn)一維數(shù)組height 中下標(biāo)在i+1 到j(luò) 范圍內(nèi)的所有元素的最小值。

（1） 最長(zhǎng)公共子串。給定兩個(gè)字符串A 和B，求最長(zhǎng)公共子串。

『解析』先將第二個(gè)字符串寫在第一個(gè)字符串后面，中間用一個(gè)沒有出現(xiàn)過(guò)的字符隔開，再求這個(gè)新的字符串的后綴數(shù)組。當(dāng)suffix(sa[i-1]) 和suffix(sa[i])不是同一個(gè)字符串中的兩個(gè)后綴時(shí)，max{height[i]}才是滿足條件

..代碼 二段 有一種WA了1萬(wàn)次才過(guò) #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <ctime> #include <algorithm> #include <iostream> #include <sstream> #include <string> #define oo 0x13131313 using namespace std;/**suffix array*倍增算法 O(n*logn)*待排序數(shù)組長(zhǎng)度為n,放在0~n-1中，在最后面補(bǔ)一個(gè)0*build_sa( ,n+1, );//注意是n+1;*getHeight(,n);*例如：*n = 8;*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位為0，其他大于0*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]為有效值，rank[n]必定為0無(wú)效值*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]為有效值，sa[0]必定為n是無(wú)效值*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]為有效值**/ const int MAXN=300000+5; char S1[MAXN],S2[MAXN]; int sa[MAXN]; int t1[MAXN],t2[MAXN],c[MAXN]; int rank[MAXN],height[MAXN]; void build_sa(int s[],int n ,int m) {int i,j,p,*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=0;i<m;i++) c[i]+=c[i-1];for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(j=1;j<=n;j<<=1){p=0;for(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++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=0;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(i=1;i<n;i++)x[sa[i]]=(y[sa[i-1]]==y[sa[i]])&&(y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;if(p>=n) break;m=p;} } int s[MAXN]; int len1,len2,ans=0; void getHeight(int s[],int n) {int i,j,k=0;for(i=0;i<=n;i++)rank[sa[i]]=i;for(i=0;i<n;i++){if(k)k--;j=sa[rank[i]-1];while(s[i+k]==s[j+k])k++;height[rank[i]]=k;} } int main() {// freopen("a.in","r",stdin);// freopen("a.out","w",stdout);while(scanf("%s",S1)!=EOF){int ans=0;len1=strlen(S1);scanf("%s",S2);len2=strlen(S2);for(int i=0;i<len1;i++) s[i]=S1[i];s[len1]='$';for(int i=len1+1;i<=len2+len1+1;i++) s[i]=S2[i-len1-1];build_sa(s,len1+len2+2,256);getHeight(s,len1+len2+1);for(int i=2;i<=len1+len2+1;i++){int MAX=max(sa[i-1],sa[i]);int MIN=min(sa[i-1],sa[i]);if(MAX>len1&&MIN<len1){if(ans<height[i])ans=height[i];}}cout<<ans<<endl;} }
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <ctime> #include <algorithm> #include <iostream> #include <sstream> #include <string> #define oo 0x13131313 using namespace std;/**suffix array*倍增算法 O(n*logn)*待排序數(shù)組長(zhǎng)度為n,放在0~n-1中，在最后面補(bǔ)一個(gè)0*build_sa( ,n+1, );//注意是n+1;*getHeight(,n);*例如：*n = 8;*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位為0，其他大于0*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]為有效值，rank[n]必定為0無(wú)效值*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]為有效值，sa[0]必定為n是無(wú)效值*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]為有效值**/ const int MAXN=300000+5; char S1[MAXN],S2[MAXN]; int sa[MAXN]; int t1[MAXN],t2[MAXN],c[MAXN]; int rank[MAXN],height[MAXN]; void build_sa(int s[],int n ,int m) {int i,j,p,*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=0;i<m;i++) c[i]+=c[i-1];for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(j=1;j<=n;j<<=1){p=0;for(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++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=0;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(i=1;i<n;i++)x[sa[i]]=(y[sa[i-1]]==y[sa[i]])&&(y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;if(p>=n) break;m=p;} } int s[MAXN]; int len1,len2,ans=0; void getHeight(int s[],int n) {int i,j,k=0;for(i=0;i<=n;i++)rank[sa[i]]=i;for(i=0;i<n;i++){if(k)k--;j=sa[rank[i]-1];while(s[i+k]==s[j+k])k++;height[rank[i]]=k;} } int main() {//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);while(scanf("%s",S1)!=EOF){int ans=0;len1=strlen(S1);scanf("%s",S2);len2=strlen(S2);for(int i=0;i<len1;i++) s[i]=S1[i];s[len1]='@';for(int i=len1+1;i<=len2+len1+1;i++) s[i]=S2[i-len1-1];build_sa(s,len1+len2+2,128);getHeight(s,len1+len2+1);for(int i=2;i<=len1+len2+1;i++){if((long long)(sa[i]-len1)*(long long)(sa[i-1]-len1)<0) //乘爆了long long WA了無(wú)數(shù)發(fā) 真是酸爽{if(ans<height[i])ans=height[i];}}cout<<ans<<endl;} }

轉(zhuǎn)載于:https://www.cnblogs.com/zy691357966/p/5480325.html

總結(jié)

以上是生活随笔為你收集整理的【后缀数组】【poj2774】【 Long Long Message】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。