poj 2774(后缀数组)

poj 2774

给出两个字符串,求这两个字符串的公共子串。

我们可以连接两个字符串,中间插入$\$$,然后构造后缀数组,用$height$数组解决。

以abbbc和bbc为例。

因为后缀数组是字典序排的,所以排名最近的两个后缀拥有的最大公共前缀一定比不相邻的长。所以,由图可知,只要后缀$i$的位置在串1的范围,后缀$i-1$在串2的范围(反过来亦可),那么就可以用$height[i]$更新$ans$的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj2774"
using namespace std;
const int MAXN = 100000 + 5;
char s1[MAXN], s2[MAXN];
int l1, l2, n, m, a[MAXN*2+100], SA[MAXN*2+100], rk[MAXN*2+100], tp[MAXN*2+100], height[MAXN*2+100], tax[MAXN*2+100];
bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
void build() {
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
int p;
for (int k=1;k<=n;k*=2) {
p = 0;
for (int i=n-k;i<n;i++) tp[p++] = i;
for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];
swap(rk, tp), rk[SA[0]] = 0, p = 0;
for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
if (++p>=n) break;
m = p;
}
}
void getH() {
int k = 0;
for (int i=0;i<n;i++) {
if (k) k--;
int j = SA[rk[i]-1];
while (a[i+k]==a[j+k]) k++;
height[rk[i]] = k;
}
}
void init() {
scanf("%s", s2);
l1 = strlen(s1), l2 = strlen(s2);
n = l1 + l2 + 2, m = 128;
for (int i=0;i<l1;i++) a[i] = s1[i];
a[l1] = '$', a[n-1] = 0;
for (int i=0;i<l2;i++) a[l1+1+i] = s2[i];
}
void solve() {
build(), getH();
int ans = 0;
for (int i=2;i<n;i++) if (height[i]>ans) {
if ((0<=SA[i]&&SA[i]<l1&&SA[i-1]>l1) || (0<=SA[i-1]&&SA[i-1]<l1&&SA[i]>l1)) ans = height[i];
//i在第一个字符串内,i-1在第二个字符串内
//或者i-1在第一个字符串内,i在第二个字符串内
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen("1.out","w",stdout);
#endif
while(scanf("%s", s1)==1) init(), solve();
return 0;
}

------ 本文结束 ------