POJ

题意：

求两个字符串的最长公共子串的长度。
思路：

利用后缀数组中 height[] 的意义，将两个字符串拼接为一个字符串，中间插入特殊符号；然后求得来自两个不同串的后缀的最长公共前缀即可。
 1 /*
 2 * @Author: WindyStreet
 3 * @Date:   2018-07-31 14:30:43
 4 * @Last Modified by:   WindyStreet
 5 * @Last Modified time: 2018-07-31 14:37:47
 6 */
 7 #include<bits/stdc++.h>
 8 
 9 using namespace std;
10 
11 #define X first
12 #define Y second
13 #define eps  1e-2
14 #define gcd __gcd
15 #define pb push_back
16 #define PI acos(-1.0)
17 #define lowbit(x) (x)&(-x)
18 #define bug printf("!!!!!
");
19 #define mem(x,y) memset(x,y,sizeof(x))
20 
21 typedef long long LL;
22 typedef long double LD;
23 typedef pair<int,int> pii;
24 typedef unsigned long long uLL;
25 
26 const int maxn = 2e5+7;
27 const int INF  = 1<<30;
28 const int mod  = 1e9+7;
29 char s[maxn],tmp[maxn];
30 int sa[maxn],h[maxn],rk[maxn],c[maxn],t[maxn],t2[maxn];
31 void work(int n,int m){
32     int i, *x = t, *y = t2;
33     //基数排序
34     for(i = 0; i < m; i++) c[i] = 0;
35     for(i = 0; i < n; i++) c[x[i]=s[i]]++;
36     for(i = 1; i < m; i++) c[i] += c[i-1];
37     for(i = n -1; i >= 0; i--) sa[--c[x[i]]] = i;
38     for(int k = 1; k <= n; k <<= 1){
39         int p = 0 ;
40         for(i = n - k; i < n; i++) y[p++] = i;
41         for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
42         for(i = 0; i < m; i++) c[i] = 0;
43         for(i = 0; i < n; i++) c[x[y[i]]]++;
44         for(i = 0; i < m; i++) c[i] += c[i-1];
45         for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
46         swap(x,y);
47          p = 1; x[sa[0]] = 0;
48          for(i = 1; i < n ;i++){
49              x[sa[i]] = y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k] ? p-1:p++;
50          }
51          if(p>=n)break;
52          m = p;
53     }
54     int k = 0;
55     for(i = 0; i < n; i++) rk[sa[i]] = i;
56     for(i = 0; i < n; i++){
57         if(k) k--;
58         int j = sa[rk[i]-1];
59         while(s[i+k]==s[j+k])k++;
60         h[rk[i]] = k;
61     }
62 }
63 
64 void solve(){
65     scanf("%s",s);
66     scanf("%s",tmp);
67     int len = strlen(s);
68     int len1= strlen(tmp);
69     s[len] = '#';                                 //中间插入特殊字符
70     for(int i = 0;i<len1;i++){
71         s[len+i+1] = tmp[i];
72     }
73     s[len + len1+1] = '';
74     work(len+len1+1,128);
75     int ans = 0;
76     for(int i=2;i<=len+len1+1;i++){
77         if(1LL*(sa[i] - len)*1ll*(sa[i-1] - len)<0)        //判断是否来自两个不同的串
78             ans = max(ans, h[i]);
79     }
80     printf("%d
",ans);
81     
82     return;
83 }
84 
85 int main()
86 {
87 //    freopen("in.txt","r",stdin);
88 //    freopen("out.txt","w",stdout);
89 //    ios::sync_with_stdio(false);
90     int t = 1;
91     //scanf("%d",&t);
92     while(t--){
93     //    printf("Case %d: ",cas++);
94         solve();
95     }
96     return 0;
97 }