学后缀数组后的一道裸题。先来讲讲收获,作为字符串初学者,后缀数组也是刚刚在学,所幸的是有一篇好的论文《后缀数组--处理字符串的有力工具》by 罗穗骞,里面非常详尽地介绍了有关后缀数组的概念,也就是sa[i]和rk[i]表示的是什么。理解了它们互为逆运算后就不难理解sa[rk[i]]=i rk[sa[i]]=i,所以知道其中一个就可以知道另外一个,然后学习了一下后缀数组中的倍增算法构建,虽然效率比不上线性的算法,但是胜在好理解,好写。当然大神的代码我是不怎么懂,我就翻阅了另一本书《挑战程序设计竞赛》里的代码,总之就是两个材料一起看,搞懂了什么是高度数组lcp, 也知道了h[i]>=h[i-1]-1,理解这个不等式我觉得挺关键的,利用这一点就可以写出一个线性的算法求出高度数组。高度数组的一个应用就是求两个串的最长公共子串。对于S1和S2,我们构造一个新串S1#S2,然后建立后缀数组,求出lcp,可以证明的是,最长公共前缀一定是出现在后缀数组中相邻的两个子串里的(否则越离越远,只可能更小)。利用这一点,我们找出满足sa[i]和sa[i+1]分属于S1,S2的串,然后对应的lcp[i]的最大值就是答案。代码完全参(zhao)考(chao)挑战程序设计竞赛,写下来权当学习。。
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#pragma warning(disable:4996) #include<iostream> #include<cstring> #include<algorithm> #include<string> #include<vector> #include<cmath> #include<cstdio> #define maxn 500000 using
namespace std;
int
rk[maxn+50], sa[maxn+50],lcp[maxn+50];
int
tmp[maxn + 50];
int
k,n;
bool
cmp_sa( int
i, int
j)
{ if
(rk[i] != rk[j]) return
rk[i] < rk[j];
else
{
int
ri = i + k <= n ? rk[i + k] : -1;
int
rj = j + k <= n ? rk[j + k] : -1;
return
ri < rj;
}
} void
construct_sa( char
*s, int
*sa)
{ n = strlen (s);
for
( int i = 0; i <= n; i++){
sa[i] = i;
rk[i] = i < n ? s[i] : -1;
}
for
(k = 1; k <= n; k <<= 1)
{
sort(sa, sa + n + 1, cmp_sa);
tmp[sa[0]] = 0;
for
( int i = 1; i <= n; i++)
{
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for
( int i = 0; i <= n; i++){
rk[i] = tmp[i];
}
}
} void
construct_lcp( char
*s, int
*sa, int
*lcp)
{ n = strlen (s);
for
( int i = 0; i <= n; i++) rk[sa[i]] = i;
int
h = 0;
lcp[0] = 0;
for
( int i = 0; i < n; i++){
int
j = sa[rk[i] - 1];
for
(h ? h-- : 0; j + h < n&&i + h < n&&s[j + h] == s[i + h]; h++);
lcp[rk[i] - 1] = h;
}
} char
str1[maxn + 50], str2[maxn + 50];
int
main()
{ int
T; cin >> T; getchar ();
while
(T--)
{
gets (str1);
gets (str2);
int
len = strlen (str1);
str1[len] = ‘#‘ ;
str1[len + 1] = ‘\0‘ ;
strcat (str1, str2);
construct_sa(str1 ,sa);
construct_lcp(str1,sa,lcp);
int
ans = 0;
for
( int i = 0; i < strlen (str1); i++)
{
if
((sa[i] < len) != (sa[i + 1]) < len){
ans = max(ans, lcp[i]);
}
}
printf ( "Nejdelsi spolecny retezec ma delku %d.\n" , ans);
}
return
0;
} |