Long Long Message
题意：求两个串的最长公共字串。
用特殊符号连接两个字符串，后缀数组。
枚举height，如果sa[i]和sa[i-1]分别属于不同的串，则更新最大值。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 200010; 7 char s[maxn]; 8 int sa[maxn],t1[maxn],t2[maxn],c[maxn]; 9 int rank[maxn],height[maxn]; 10 11 12 void build_sa(int n, int m){ 13 int i, *x = t1, *y = t2; 14 for(i = 0; i < m; i++) c[i] = 0; 15 for(i = 0; i < n; i++) c[x[i] = s[i]]++; 16 for(i = 1; i < m; i++) c[i] += c[i-1]; 17 for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; 18 for(int k = 1; k <= n; k <<= 1){ 19 int p = 0; 20 for(i = n-k; i < n; i++) y[p++] = i; 21 for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k; 22 for(i = 0; i < m; i++) c[i] = 0; 23 for(i = 0; i < n; i++) c[x[y[i]]]++; 24 for(i = 1; i < m; i++) c[i] += c[i-1]; 25 for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; 26 swap(x,y); 27 p=1; 28 x[sa[0]]=0; 29 for(i = 1; i < n; i++) 30 x[sa[i]]= y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? p-1 : p++; 31 if(p >= n) break; 32 m=p; 33 } 34 } 35 void getHeight(int n){ 36 int i, j, k=0; 37 for(i = 0; i <= n; i++) rank[sa[i]] = i; 38 for(i = 0; i < n; i++) { 39 if(k) k--; 40 j = sa[rank[i]-1]; 41 while(s[i+k]==s[j+k]) k++; 42 height[rank[i]] = k; 43 } 44 } 45 46 int main(){ 47 while(scanf("%s",s)!=EOF){ 48 int n=strlen(s); 49 int l1=n; 50 s[n]='#'; 51 scanf("%s",s+n+1); 52 n=strlen(s); 53 // cout<<s<<endl; 54 build_sa(n+1,256); 55 getHeight(n); 56 int ans=0; 57 for(int i = 1; i < n; i++){ 58 if(sa[i]<l1&&sa[i-1]>l1 || sa[i]>l1&&sa[i-1]<l1){ 59 ans=max(ans,height[i]); 60 } 61 } 62 printf("%d ",ans); 63 } 64 return 0; 65 }