http://poj.org/problem?id=2774

題解：后綴數組+最長公共子串

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=200000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,u,v; int ans,cnt,flag,temp,sum; int r[N],c[N],x[N],y[N],sa[N],ra[N],height[N]; char str1[N],str2[N]; struct node{}; void SA(int n,int m){for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]=r[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;for(int k=1;k<=n;k<<=1){int num=0;for(int i=n-k+1;i<=n;i++)y[++num]=i;for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;swap(x,y);x[sa[1]]=1;num=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;if(num==n)break;m=num;} } void getheight(int n){int k=0;for(int i=1;i<=n;i++)ra[sa[i]]=i;for(int i=1;i<=n;i++){if(k)k--;int j=sa[ra[i]-1];while(r[i+k]==r[j+k])k++;height[ra[i]]=k;} } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){//scanf("%d",&n);while(~scanf("%s%s",str1+1,str2+1)){int len1=strlen(str1+1);int len2=strlen(str2+1);for(int i=1;i<=len1;i++)r[i]=str1[i]-'a'+1;r[len1+1]=27;for(int i=1;i<=len2;i++)r[i+len1+1]=str2[i]-'a'+1;int len=len1+len2+2;r[len]=0;SA(len,27);getheight(len);ans=-INF;for(int i=2;i<=len;i++){if((sa[i]<=len1)!=(sa[i-1]<=len1)){ans=max(ans,height[i]);}}cout<<ans<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

總結

以上是生活随笔為你收集整理的Long Long Message的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。