题意：给出两个字符串，求最长公共子串的长度。
分析：一道后缀数组的题，构造后缀数组有两种算法，dc3和倍增，效率分别为O(n)和O(nlogn)，但前者的实现较困难。后缀数组构造后获得了3个数组，sa[i]表示所有后缀排序后的排在第i位的后缀，rank[i]表示原串从第i位到结尾的那个后缀在sa中的排名是多少。height[i]表示sa[i]和sa[i + 1]所表示的字符串的最长公共前缀的长度。本题可以利用height来做，先把两个串连接，找最大height。但是记得在把两个字符串连接时加一个特殊字符作分隔。并注意判断两个sa起始位置不在一个串的内部。之所以要加这个分隔符，首先是可以保证我们所求的两个串的起始位置在sa中是相邻的，如果不加入这个分隔符，答案中两个子串在sa中可能中间会出现一些横跨两个字符串的后缀，遇到这种不相邻的情况，需要用height在两串之间的最小值外加复杂的两串是否合法匹配的判断，例如：aaba,abaaba。如果没有判断好可能会出现abaabaaba与abaaba的匹配。而且这样一来求区间内height最小值的复杂度至少是O(nlogn)（用rmq）。
View Code #include < iostream > #include < cstdlib > #include < cstring > #include < cstdio > using namespace std; #define N 200000 char s[N]; // N > 256 int n, sa[N], height[N], rank[N], tmp[N], top[N]; void makesa(){ // O(N * log N) int i, j, len, na; na = (n < 256 ? 256 : n); memset(top, 0 , na * sizeof ( int )); for (i = 0 ; i < n; i ++ ) top[rank[i] = s[i] & 0xff ] ++ ; for (i = 1 ; i < na; i ++ ) top[i] += top[i - 1 ]; for (i = 0 ; i < n; i ++ ) sa[ -- top[rank[i]]] = i; for (len = 1 ; len < n; len <<= 1 ) { for (i = 0 ; i < n; i ++ ) { j = sa[i] - len; if (j < 0 ) j += n; tmp[top[rank[j]] ++ ] = j; } sa[tmp[top[ 0 ] = 0 ]] = j = 0 ; for (i = 1 ; i < n; i ++ ) { if (rank[tmp[i]] != rank[tmp[i - 1 ]] || rank[tmp[i] + len] != rank[tmp[i - 1 ] + len]) top[ ++ j] = i; sa[tmp[i]] = j; } memcpy(rank, sa, n * sizeof ( int )); memcpy(sa, tmp, n * sizeof ( int )); if (j >= n - 1 ) break ; }} void lcp(){ // O(4 * N) int i, j, k; for (j = rank[height[i = k = 0 ] = 0 ]; i < n - 1 ; i ++ , k ++ ) while (k >= 0 && s[i] != s[sa[j - 1 ] + k]) height[j] = (k -- ), j = rank[sa[j] + 1 ];} int main(){ // freopen("D:\\t.txt", "r", stdin); gets(s); int l1 = strlen(s); s[l1] = ' $ ' ; gets(s + l1 + 1 ); int len; n = len = strlen(s); n ++ ; s[n] = ' $ ' ; makesa(); lcp(); int ans = 0 ; for ( int i = 0 ; i < n; i ++ ) if ((sa[i] < l1 && sa[i - 1 ] > l1) || (sa[i] > l1 && sa[i - 1 ] < l1)) if (height[i] > ans) ans = height[i]; printf( " %d\n " , ans); return 0 ;}