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

2019-11-14 09:10:12

字體：大中小

來源：轉載

供稿：網友

題目鏈接：

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 200010char 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]; }