POJ 2774 & URAL 1517（最长公共子串）

题目链接：

URAL-1517 POJ-2774

题目大意：

就是给两个字符串，求最长公共子串。

解题思路：

法一：常规动态规划

好像是可以的（虽然我自己没试(～￣▽￣)～） 因为常规的LCS是O(n^2)的，所以讲LCS转化成LIS，就可以在O(n log n)的时间内完成。 具体的讲解看:LCS的nlogn法

法二：后缀数组

这个方法非常好，好像处理后缀数组可以使用O(n)或O(n log n) 不过后来查询的时候可以做到O(n)

先将两个字符串用 “#” 连接起来，比如 ‘abab’ + ‘nskfn’ —> ‘abab#nskfn’再来求他们的后缀数组，包括height的值，然后查询每个height，记录符合条件的最大值（条件：sa[i-1]和sa[i]在连接”#”的两侧） 然后就ok了。。。(＾－＾)V

下面是代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define rep(i,x,y) for(int i = x;i <= y;i++) #define dep(i,x,y) for(int i = x;i >= y;i--) #define N 200010 char str[N]; int sa[N],r[N],h[N],s[N]; int l1,l2,n; void read() { scanf("%s",str); l1 = strlen(str); rep(i,0,l1-1) s[i] = str[i]; s[l1] = '$'; scanf("%s",str); l2 = strlen(str); rep(i,l1+1,l1+l2) s[i] = str[i - l1 - 1]; s[n = l1+l2+1] = 0; } int c[N],t[N],t1[N]; void build(int n,int m) { int *x = t,*y = t1; rep(i,0,m-1) c[i] = 0; rep(i,0,n-1) c[x[i] = s[i]] ++; rep(i,1,m-1) c[i] += c[i-1]; for(int i = n-1;i >= 0;i--) sa[--c[x[i]]] = i; int p = 1; for(int k = 1;k < n;k <<= 1) { p = 0; rep(i,n-k,n-1) y[p++] = i; rep(i,0,n-1) if(sa[i] >= k) y[p++] = sa[i] - k; rep(i,0,m-1) c[i] = 0; rep(i,0,n-1) c[ x[y[i]] ]++; rep(i,1,m-1) c[i] += c[i-1]; for(int i = n-1;i >= 0;i--) sa[--c[ x[y[i]]]] = y[i]; swap(x,y);p = 1;x[sa[0]] = 0; rep(i,1,n-1) x[sa[i]] = y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? p-1 : p++; if(p >= n) break; m = p; } } void getheight() { rep(i,1,n) r[sa[i]] = i; int k = 0; rep(i,0,n) { if(k) k--; int j = sa[r[i]-1]; while(s[i+k] == s[j+k]) k++; h[r[i]] = k; } } int main() { read(); build(n+1,200); getheight(); int maxn = 0; rep(i,1,n) if(h[i] > maxn) { if(sa[i-1] < l1 && sa[i] > l1) maxn = h[i]; if(sa[i-1] > l1 && sa[i] < l1) maxn = h[i]; } printf("%d",maxn); return 0; }