题意：判断给定的两个串中，最长的公共串。 思路：将它们合并为一个串，中间用特殊字符隔开， 然后利用后缀数组求解。
封装版的 用的倍增算法 时间复杂度O（nlogn） +Ｏ（ｎ）
#include "cstdio" #include "cstring" #define P 20 #define MAXN 1000005 #define min(a, b) ((a) < (b) ? (a) : (b)) typedef class Suffix_Array { private: short flag = 0; int n, a[MAXN], b[MAXN], c[MAXN], sa[MAXN], height[MAXN], rank[MAXN], log2[MAXN], st[MAXN][P]; inline void Rmq_Init(int* a, int n) { for(register int i = 2; i <= n; ++i) log2[i] = log2[i >> 1] + 1; for(register int i = 0; i <= n; ++i) st[i][0] = a[i]; for(register int i, j = 1, len; j <= log2[n]; ++j) for(i = 0, len = (1 << j); i + len - 1 <= n; ++i) st[i][j] = min(st[i + (len >> 1)][j - 1], st[i][j - 1]); } inline int Ask_Rmq(int l, int r) { static int k; if(l > r) { l ^= r ^= l ^= r; } k = log2[r - l + 1]; return min(st[l][k], st[r - (1 << k) + 1][k]); } public: void build(char* s, int n, int m) { int *x = a, *y = b, *t; this -> n = n; for(register int i = 0; i < m; c[i++] = 0); for(register int i = 0; i < n; ++c[x[i] = s[i++]]); for(register int i = 1; i < m; ++i) c[i] += c[i - 1]; for(register int i = n - 1; ~i; sa[--c[x[i]]] = i--); for(register int i, k = 1, p = 1; p < n && k <= n; k <<= 1, m = p) { for(p = 0, i = n - k; i < n; y[p++] = i++); for(i = 0; i < n; sa[i] >= k ? y[p++] = sa[i++] - k : ++i); for(i = 0; i < m; c[i++] = 0); for(i = 0; i < n; ++c[x[y[i++]]]); for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; ~i; sa[--c[x[y[i]]]] = y[i--]); for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++; } for(register int i = 0; i < n; rank[sa[i]] = i++); for(register int i = 0, k = 0, j; i < n; height[rank[i++]] = k) for(k ? --k : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k); } inline int Lcp(int l, int r) { if( !flag ) { Rmq_Init(height, n); flag = 1; } return Ask_Rmq(rank[l] + 1, rank[r]); } inline int Lcs(int len1) { int ans = 0; for(register int i = 2; i < n; ++i) { if(ans < height[i]) if((sa[i] > len1 && sa[i-1] < len1) || (sa[i] < len1 && sa[i-1] > len1)) ans = height[i]; } return ans; } } Suffix; char s[MAXN]; int ans, len1, len2; Suffix Sa; int main() { while( ~scanf("%s", s) ) { len1 = strlen(s); s[len1] = '$'; scanf("%s", s + len1 + 1); len2 = strlen(s); Sa.build(s, len2 + 1, 300); printf("%d\n", Sa.Lcs(len1)); } }78ms
另一个还是78ms
#include "cstdio" #include "cstring" int a[1000005], b[1000005], c[1000005], sa[1000005], height[1000005], rank[1000005]; void build(char* s, int n, int m) { int *x = a, *y = b, *t; register int i, j, k, p; for(i = 0; i < m; c[i++] = 0); for(i = 0; i < n; ++c[x[i] = s[i++]]); for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; ~i; sa[--c[x[i]]] = i--); for(i, k = 1, p = 1; p < n && k <= n; k <<= 1, m = p) { for(p = 0, i = n - k; i < n; y[p++] = i++); for(i = 0; i < n; sa[i] >= k ? y[p++] = sa[i++] - k : ++i); for(i = 0; i < m; c[i++] = 0); for(i = 0; i < n; ++c[x[y[i++]]]); for(i = 1; i < m; ++i) c[i] += c[i - 1]; for(i = n - 1; ~i; sa[--c[x[y[i]]]] = y[i--]); for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++; } for(i = 0; i < n; rank[sa[i]] = i++); for(i = 0, k = 0, j; i < n; height[rank[i++]] = k) for(k ? --k : 0, j = sa[rank[i] - 1]; s[i + k] == s[j + k]; ++k); } char s[1000005]; int ans, len1, len2; int main() { while( ~scanf("%s", s) ) { len1 = strlen(s); s[len1] = '$'; scanf("%s", s + len1 + 1); len2 = strlen(s); build(s, len2 + 1, 128); ans = 0; for(register int i = 2; i < len2; ++i) { if(ans < height[i]) if((sa[i] > len1 && sa[i-1] < len1) || (sa[i] < len1 && sa[i-1] > len1)) ans = height[i]; } printf("%d\n", ans); } }