字符串的任何一个子串都是该字符串某个后缀的前缀。
两个字符串的最长公共子串可转化为，求两者后缀两两比较的最长公共前缀的最大值。
定义：
后缀数组(sa[])，名次数组(rank[])：
子串str(i...n)(1 <= i <= n)是原字符串str(1...n)的第i个后缀。
对所有的后缀进行排序（字典序），得到第i个子串的名次rank[i]，则定义sa[rank[i]] = i，即名次排在第i位的后缀是第几个。
height数组：
名次相邻的两个后缀的最长公共前缀的长度。
另外补充一个h数组，h[i] = height[rank[i]]。
倍增法求解sa数组：
例如串”aabaaaab”，则所有子串为：
aabaaaab
abaaaab
baaaab
aaaab
aaab
aab
ab
b
现在对上面8个子串进行排序。
1.首先排长度为1的元素
（此处标号为x数组中存储信息。）
（在考虑到其在字符串中顺序，实际代码实现过程中，真正的名次标号为1 2 7 3 4 5 6 8，这样sa数组才不会产生冲突。）
（sa数组此时标号为1 2 4 5 6 7 3 8）
2.排长度为2的元素
首先对第二关键字，即图中的y，得到次序为（利用sa中信息）：
b0 aa aa aa aa ab ab ba
然后对第一关键字排序（0元素不可能做第一关键字）：
a：aa aa aa aa ab ab
b：b0 ba
所以排完之后第一关键字后得到的次序为：
aa aa aa aa ab ab b0 ba
（sa数组此时标号为1 4 5 6 2 7 8 3）
（此时的位置可以理解为：每个块的起始位置点。）
观察发现，长度为l的某块，包含原字符串的i~l+i，那么它需要和包含字符为l+i+1~2l+i的块合并，所以合并时要注意跳过l-1个块。
合并后，长度为4的元素按字符串中出现次序排列是：
aaba abaa baaa aaaa aaab aab0 ab00 b000
按第二关键字（aa ab ba b0 00）排序后得（利用sa中信息）
00：ab00 b000
aa：abaa baaa aaaa
ab：aaab
b0：aab0
ba：aaba
得到排序：ab00 b000 abaa baaa aaaa aaab aab0 aaba
再按第一关键字排序
aa：aaaa aaab aab0 aaba
ab：ab00 abaa
b0：b000
ba：baaa
于是长度为4的元素也排好了：
aaaa aaab aab0 aaba ab00 abaa b000 baaa
（同样，新出的名次将会更新sa数组，下一次排长度为8的块时，可利用sa的信息o(1)得解长度为4的块的名次。）
4.接下来排长度为8的元素
原始顺序：
aabaaaab abaaaab0 baaaab00 aaaab000 aaab0000 aab00000 ab000000 b0000000
按第二关键字：
0000：aaab0000 aab00000 ab000000 b0000000
aaaa：
aaab：aabaaaab
aab0：abaaaab0
aaba：
ab00：baaaab00
abaa：aaaab000
b000：
baaa：
排序后为： aaab0000 aab00000 ab000000 b0000000 aabaaaab abaaaab0 baaaab00 aaaab000
按第一关键字：
aaaa：aaaab000
aaab：aaab0000
aab0：aab00000
aaba：aabaaaab
ab00：ab000000
abaa：abaaaab0
b000：b0000000
baaa：baaaab00
排序后：aaaab aaab aab abaaaab abaaaa b baaaa
这一次更新sa数组后，就真正得到了所有后缀的排序。
四个辅助数组加上一个sa数组和一个原数组，需要的空间为6n，时间复杂度为o(nlogn)。
其中wc数组的空间是可以节省下来的，只要将每个wc[i]替换为x[y[i]]即可。
接下来，求解两个任意两个后缀间的最长公共前缀：
surffix(a)和surffix(b)代表从位置a开始的后缀和从位置b开始的后缀。
对于任意名次的rank[j]和rank[k]，surffix(rank[j])和surffix(rank[k])之间的最长公共前缀一定是surffix(rank[j]) 和surffix(rank[j]+1)、 surffix(rank[j]+1)和 surffix(rank[j]+2)、... 、surffix(rank[k] - 1)和surffix(rank[k])之间的最小值。
surffix(sa[rank[i-1]])和surffix(sa[rank[i]])最长公共前缀长度为h[i]。
那么当h[i] > 0时(此时至少首字符相同)，那么surffix(sa[rank[i-1]]))和surffix(sa[rank[i]]))同时去掉首字符之后得到的surffix(k1)和surffix(k2)之间的最长公共前缀是h[i]-1，且surffix(k1) 的名次一定排在surffix(k2) 前面。
如果首字符不同，则h[i-1] = 0，而h[i] >= 0。所以对于任意的h[i]都有h[i] >= h[i-1] -1。
按照rank的顺序，我们可以不用比较surffix(rank[i])和surffix(rank[i+1])前面h[i]个字符，因为他们一定是匹配的。
height中的最大值并不是题目所求，必须保证取值的height是来自两个不同部分。
分裂地将两者后缀两两比较，复杂度将达到o(n^2)。于是将两个字符串拼接起来，中间用一个从未出现的字符隔开。对新的字符串的后缀求height，中间插入的字符保证，求得的height不会越过插入字符的位置。
参考文献：
[1] 罗穗骞，《后缀数组——处理字符串的有力工具》
[2] 刘汝佳，《算法竞赛入门经典》
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 200010
int sa[MAXN], r[MAXN];
int wa[MAXN], wb[MAXN], wc[MAXN], wd[MAXN];
int cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m)
{
int *x = wa, *y = wb;
for(int i = 0; i < m; i++) wd[i] = 0;
for(int i = 0; i < n; i++) wd[x[i] = r[i]]++;
for(int i = 1; i < m; i++) wd[i] += wd[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--wd[x[i]]] = i;
for(int j = 1, p = 0; p < n; j *= 2, m = p)
{
p = 0;
for(int i = n - j; i < n; i++) y[p++] = i;
for(int i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
for(int i = 0; i < n; i++) wc[i] = x[y[i]];
for(int i = 0; i < m; i++) wd[i] = 0;
for(int i = 0; i < n; i++) wd[wc[i]]++;
for(int i = 1; i < m; i++) wd[i] += wd[i - 1];
for(int i = n - 1; i >= 0; i--) sa[--wd[wc[i]]] = y[i];
swap(x, y), p = 1, x[sa[0]] = 0;
for(int i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
return ;
}
int rank[MAXN], height[MAXN];
void calheight(int n)
{
for(int i = 1; i <= n; i++) rank[sa[i]] = i;
for(int i = 0, k = 0, j; i < n; i++)
{
if(k) k--;
j = sa[rank[i] - 1];
while(r[i + k] == r[j + k]) k++;
height[rank[i]] = k;
}
}
char str[MAXN];
int main()
{
// freopen("2774.in", "r", stdin);
int k = 0;
scanf("%s", str);
int l1 = strlen(str);
for(int i = 0; i < l1; i++, k++) r[k] = str[i] - 'a' + 2;
r[k++] = 1; ///添加'$'符号
scanf("%s", str);
int l2 = strlen(str);
for(int i = 0; i < l2; i++, k++) r[k] = str[i] - 'a' + 2;
r[k++] = 0;
da(r, sa, k, 30);
calheight(k - 1);
int ans = 0;
for(int i = 2; i < k; i++)
if((sa[i] < l1 && sa[i - 1] > l1) || (sa[i - 1] < l1 && sa[i] > l1))
ans = max(ans, height[i]);
printf("%d\n", ans);
return 0;
}