<span>POJ - 2774 Long Long Message</span>
传送门：POJ - 2774 （最长相同子串）
题意：（在vj上看到了一个很有意思的描述）
L学长喜欢上Z学妹，他发现他们的相似度很高，担心会不会就那么巧合，所以就想办法弄到了Z学妹的基因，然后也把自己的基因一起拿去比对，希望找出基因中完全一样的一段的最大长度，来判断要不要去德国骨科。
题解：把两个字符串拼一起，中间加一个分隔的字符（字符串里不会出现的字符）。为什么要加分隔字符呢，因为可能会出现这种结果，前一个字符串的尾部和后一个的首部连一起形成的字符串，和后一个剩下的某部分正好一样，导致判断难度加大。加了分隔符就相当于直接剪断了他们相等的可能。然后求出height数组，遍历 height数组 ，先判断height值是否比当前的最大值大，然后判断此时的sa[i-1]是否小于，sa[i]是否大于第一个字符串的长度，如果都满足就可以将最大值更新。
最近迷上了二分的做法，然后发现二分多此一举了，，，
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #include<iostream> 5 #include<cmath> 6 #include<cstring> 7 using namespace std; 8 9 const int INF=0x3f3f3f3f; 10 const int maxn = 1e6+10; 11 int wa[maxn],wb[maxn],wsf[maxn],wv[maxn],sa[maxn]; 12 int rnk[maxn],height[maxn]; 13 char s[maxn],t[maxn]; 14 int r[maxn],n,ans=0,len1,len2; 15 16 //sa:字典序中排第i位的起始位置在str中第sa[i] sa[1~n]为有效值 17 18 //rnk:就是str第i个位置的后缀是在字典序排第几 rnk[0~n-1]为有效值 19 20 //height：字典序排i和i-1的后缀的最长公共前缀 height[2~n]为有效值，第二个到最后一个 21 22 int cmp(int *r,int a,int b,int k) 23 { 24 return r[a]==r[b]&&r[a+k]==r[b+k]; 25 } 26 27 void getsa(int *r,int *sa,int n,int m)//n为添加0后的总长 28 { 29 int i,j,p,*x=wa,*y=wb,*t; 30 for(i=0; i<m; i++) wsf[i]=0; 31 for(i=0; i<=n; i++) wsf[x[i]=r[i]]++; 32 for(i=1; i<m; i++) wsf[i]+=wsf[i-1]; 33 for(i=n; i>=0; i--) sa[--wsf[x[i]]]=i; 34 p=1; 35 j=1; 36 for(; p<=n; j*=2,m=p){ 37 for(p=0,i=n+1-j; i<=n; i++) y[p++]=i; 38 for(i=0; i<=n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; 39 for(i=0; i<=n; i++) wv[i]=x[y[i]]; 40 for(i=0; i<m; i++) wsf[i]=0; 41 for(i=0; i<=n; i++) wsf[wv[i]]++; 42 for(i=1; i<m; i++) wsf[i]+=wsf[i-1]; 43 for(i=n; i>=0; i--) sa[--wsf[wv[i]]]=y[i]; 44 swap(x,y); 45 x[sa[0]]=0; 46 for(p=1,i=1; i<=n; i++) 47 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++; 48 } 49 } 50 51 void getheight(int *r,int n)//n为添加0后的总长 52 { 53 int i,j,k=0; 54 for(i=1; i<=n; i++) rnk[sa[i]]=i; 55 for(i=0; i<n; i++){ 56 if(k) 57 k--; 58 else 59 k=0; 60 j=sa[rnk[i]-1]; 61 while(r[i+k]==r[j+k]) 62 k++; 63 height[rnk[i]]=k; 64 } 65 } 66 67 bool check(int k) 68 { 69 bool flag=0; 70 int mx=-INF,mn=INF; 71 for(int i=2;i<=n;i++){ 72 if(height[i]>=k){ 73 mn=min(mn,min(sa[i],sa[i-1])); 74 mx=max(mx,max(sa[i],sa[i-1])); 75 if(mn<len1&&mx>len1) return true; 76 } 77 else mx=-INF,mn=INF; 78 } 79 return false; 80 } 81 82 int main() 83 { 84 ios::sync_with_stdio(false); 85 cin.tie(0); 86 cout.tie(0); 87 cin>>s; 88 cin>>t; 89 n=0; 90 len1=strlen(s); 91 len2=strlen(t); 92 for(int i=0;i<len1;i++) 93 r[n++]=s[i]-'a'+1; 94 r[n++]=0; 95 for(int i=0;i<len2;i++){ 96 r[n++]=t[i]-'a'+1; 97 } 98 r[n]=0; 99 getsa(r,sa,n,150); 100 getheight(r,n); 101 int ans=0; 102 for(int i=2;i<=n;i++){ 103 if(height[i]>ans){ 104 if(sa[i-1]>len1&sa[i]<len1) ans=height[i]; 105 if(sa[i]>len1&&sa[i-1]<len1) ans=height[i]; 106 } 107 } 108 cout<<ans<<endl; 109 return 0; 110 }
