题意：
给定2个字符串，求最长公共子串的长度
思路：
把两个字符串相连得到S，则他们的公共子串就是部分S的后缀子串的前缀。
因为是相同的子串，所以sa必然是相邻的，因此扫一下height，若sa[i] 与 sa[i-1] 的后缀分别在分割符$前后，那就是两个字符串的后缀，求其最长公共前缀（即height[i]）就是一个公共子串。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
#define rank Rank
/*
* 后缀数组
* DC3算法，复杂度O(n)
* 所有的相关数组都要开三倍
*待排序数组长度为n,放在0~n-1中，在最后面补一个0
*da(str ,n+1,sa,rank,height, , );//注意是n+1;
*例如：
*n = 8;
*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值
*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值
*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值
*
*/
const int MAXN=301000;
int rank[MAXN],height[MAXN];
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3],wss[MAXN*3];
int c0(int *r,int a,int b)
{
return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
}
int c12(int k,int *r,int a,int b)
{
if(k == 2)
return r[a] < r[b] || ( r[a] == r[b] && c12(1,r,a+1,b+1) );
else return r[a] < r[b] || ( r[a] == r[b] && wv[a+1] < wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i = 0;i < n;i++)wv[i] = r[a[i]];
for(i = 0;i < m;i++)wss[i] = 0;
for(i = 0;i < n;i++)wss[wv[i]]++;
for(i = 1;i < m;i++)wss[i] += wss[i-1];
for(i = n-1;i >= 0;i--)
b[--wss[wv[i]]] = a[i];
}
void dc3(int *r,int *sa,int n,int m)
{
int i, j, *rn = r + n;
int *san = sa + n, ta = 0, tb = (n+1)/3, tbc = 0, p;
r[n] = r[n+1] = 0;
for(i = 0;i < n;i++)if(i %3 != 0)wa[tbc++] = i;
sort(r + 2, wa, wb, tbc, m);
sort(r + 1, wb, wa, tbc, m);
sort(r, wa, wb, tbc, m);
for(p = 1, rn[F(wb[0])] = 0, i = 1;i < tbc;i++)
rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++;
if(p < tbc)dc3(rn,san,tbc,p);
else for(i = 0;i < tbc;i++)san[rn[i]] = i;
for(i = 0;i < tbc;i++) if(san[i] < tb)wb[ta++] = san[i] * 3;
if(n % 3 == 1)wb[ta++] = n - 1;
sort(r, wb, wa, ta, m);
for(i = 0;i < tbc;i++)wv[wb[i] = G(san[i])] = i;
for(i = 0, j = 0, p = 0;i < ta && j < tbc;p++)
sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
for(;i < ta;p++)sa[p] = wa[i++];
for(;j < tbc;p++)sa[p] = wb[j++];
}
//str和sa也要三倍
void da(int str[],int sa[],int rank[],int height[],int n,int m)
{
for(int i = n;i < n*3;i++)
str[i] = 0;
dc3(str, sa, n+1, m);
int i,j,k = 0;
for(i = 0;i <= n;i++)rank[sa[i]] = i;
for(i = 0;i < n; i++)
{
if(k) k--;
j = sa[rank[i]-1];
while(str[i+k] == str[j+k]) k++;
height[rank[i]] = k;
}
}
char str[MAXN];
int r[MAXN];
int sa[MAXN];
int main()
{
gets(str);
int len1 = strlen(str);
str[len1] = ‘$‘;
gets(str+len1+1);
int len = strlen(str), n = len;
for(int i = 0; i < n; i++)r[i] = str[i];
da(r, sa, rank, height, n, 200);
int ans = 0;
for(int i = 2; i <= n; i++)
if((sa[i] < len1 && sa[i-1] > len1) || (sa[i]>len1 && sa[i-1] < len1))
ans = max(ans , height[i]);
printf("%d\n", ans);
return 0;
}
/*
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother
abcd
stedste
aaaa
aaaa
aaaa
aaaaa
*/