高度数组:后缀数组中相邻两个后缀的最长公共前缀

  |  

摘要: 高度数组

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


$0 背景

高度数组是后缀数组中相邻两个后缀的最长公共前缀(LCP)。

1
lcp[i] := s[sa[i]..n-1] 与 s[sa[i+1]..n-1] 的最长公共前缀长度

$2 求高度数组

算法: 尺取法

lcp[i] := s[sa[i]..n-1] 与 s[sa[i+1]..n-1] 的最长公共前缀长度

首先从 sa 预处理出 rank,rank[sa[i]] = i

从位置 i = 0 的后缀开始,从前往后依次计算后缀 s[i..n-1] 与后缀 s[sa[rank[i]-1]..n-1] 的最长公共前缀长度,称为位置 i 的高度,将答案更新到 lcp[rank[i] - 1]

假设已经求得位置 i 对应的高度 h[i],则位置 i+1 对应的高度不小于 h[i]-1。因此只需要从 h[i]-1 开始计算 h[i+1]

位置 i 如果视为区间 [i, i + h[i]),每次推进 i 取区间,左右端点都不会左移,可以视为是尺取。

代码 (C++,模板)

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
vector<int> get_lcp(const string& s, const vector<int>& sa)
{
int n = s.size();
vector<int> rank(n);
for(int i = 0; i < n; ++i)
rank[sa[i]] = i;

int h = 0;
vector<int> lcp(n);
lcp[n - 1] = 0;
for(int i = 0; i < n; ++i)
{
if(rank[i] == 0)
continue;
int j = sa[rank[i] - 1];

// h 先减去首字母的 1 长度
if(h > 0)
--h;
while(j + h < n && i + h < n && s[j + h] == s[i + h])
++h;

lcp[rank[i] - 1] = h;
}
return lcp;
}

$3 高度数组应用

高度数组可以得到后缀数组内相邻两个后缀的最长公共前缀。

高度数组 + RMQ,可以得到任意两个后缀的最长公共前缀。

假设 rank[i] < rank[j],则从位置 i 和 j 开始的后缀的最长公共前缀的长度为 lcp[rank[i]], lcp[rank[i]+1], lcp[rank[j]-1] 中的最小值

(1) 最长重复子串

1062. 最长重复子串

给定字符串 S,找出最长重复子串的长度。如果不存在重复子串就返回 0。

示例 1:
输入:”abcd”
输出:0
解释:没有重复子串。

示例 2:
输入:”abbaba”
输出:2
解释:最长的重复子串为 “ab” 和 “ba”,每个出现 2 次。

示例 3:
输入:”aabcaabdaab”
输出:3
解释:最长的重复子串为 “aab”,出现 3 次。

示例 4:
输入:”aaaaa”
输出:4
解释:最长的重复子串为 “aaaa”,出现 2 次。

提示:

1
2
字符串 S 仅包含从 'a' 到 'z' 的小写英文字母。
1 <= S.length <= 1500

代码 (C++)

高度数组的最大值即最长重复子串的长度。

1
2
3
4
5
6
7
8
class Solution {
public:
int longestRepeatingSubstring(string S) {
vector<int> sa = get_sa(S);
vector<int> lcp = get_lcp(S, sa);
return *max_element(lcp.begin(), lcp.end());
}
};

1044. 最长重复子串

给你一个字符串 s ,考虑其所有 重复子串 :即 s 的(连续)子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。

示例 1:
输入:s = “banana”
输出:”ana”

示例 2:
输入:s = “abcd”
输出:””

提示:

1
2
2 <= s.length <= 3e4
s 由小写英文字母组成

代码 (C++)

前一题是求最长重复子串的长度。本题是求一个具体的最长重复子串。用字符串哈希的做法参考文章 用字符串哈希解决经典问题:最长重复子串、最长公共子串

有了高度数组之后,高度数组最大的值就是最长重复子串的长度。假设 lcp[i] 最大,则 sa[i] 即为最长重复子串的起点。

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
class Solution {
public:
string longestDupSubstring(string S) {
vector<int> sa = get_sa(S);
vector<int> lcp = get_lcp(S, sa);
int start = -1;
int max_len = 0;
int n = S.size();
for(int i = 0; i < n; ++i)
{
if(lcp[i] > max_len)
{
max_len = lcp[i];
start = sa[i];
}
}
if(start == -1)
return "";
return S.substr(start, max_len);
}

private:
const int ALPHABET = 128;

vector<int> get_sa(string_view s);
vector<int> get_lcp(string_view s, const vector<int>& sa);
};

(2) 最长公共子串

将 s 和 t 中间加一个特殊字符,连接成一个字符串,然后求最长重复子串。

(3) 最长回文子串

5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:
输入:s = “babad”
输出:”bab”
解释:”aba” 同样是符合题意的答案。

示例 2:
输入:s = “cbbd”
输出:”bb”

提示:

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母组成

算法:高度数组 + RMQ

对于长度为奇数的回文,考察串上每个位置 s[i],如果知道从 i 开始的后缀和到 i 为止的前缀翻转后的串的最长公共前缀长度,则以 i 为中心的最长子串就知道了。

因此将 s 和 s 的翻转串用特殊字符连起来得到新串 t。计算 t 的高度数组。

1
2
3
4
5
枚举 i = 0..n-1
以 i 为中心的长度为奇数的最长回文子串,求 lcp 上 rank[i] 和 rank[n * 2 - i] 之间的最大值

枚举 i = 1..n-1
以 i 为中心的且 i 在左半边的长度为偶数数的最长回文子串,求 lcp 上 rank[i] 和 rank[n * 2 - i + 1] 之间的最大值

代码 (C++,模板)

RMQ 的部分参考文章 稀疏表维护RMQ

假设 rank[i] < rank[j],则从位置 i 和 j 开始的后缀的最长公共前缀的长度为 lcp[rank[i]], lcp[rank[i]+1], lcp[rank[j]-1] 中的最小值

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
class RMQ
{
public:
RMQ(){}

void init(const vector<int>& arr)
{
int n = arr.size();
// 2 ^ m <= n
// log2(2^m) <= log2(n)
// m <= log2(n)
int m = log2(n);
dp.assign(n + 1, vector<int>(m + 1, 0));
for(int i = 0; i < n; ++i)
dp[i][0] = arr[i]; //初始化
for(int j = 1; (1 << j) <= n; ++j)
for(int i = 0; i + (1 << j) - 1 < n; ++i)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r)
{
int k = log2(r - l + 1);
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
private:
vector<vector<int>> dp;
};


class Solution {
public:
string longestPalindrome(string s) {
if(s.empty()) return "";
int n = s.size();
if(n == 1) return s;

string t = s;
reverse(s.begin(), s.end());
t += '#' + s;
vector<int> sa = get_sa(t);
vector<int> rank;
vector<int> lcp = get_lcp(t, sa, rank);

RMQ rmq;
rmq.init(lcp);

int idx = -1;
int max_len = 0;
for(int i = 0; i < n; ++i)
{
int j = n * 2 - i;
int l = rmq.query(min(rank[i], rank[j]), max(rank[i], rank[j]) - 1);
if(l * 2 + 1 > max_len)
{
max_len = l * 2 - 1;
idx = i - l + 1;
}
}
for(int i = 1; i < n; ++i)
{
int j = n * 2 - i + 1;
int l = rmq.query(min(rank[i], rank[j]), max(rank[i], rank[j]) - 1);
if(l * 2 > max_len)
{
max_len = l * 2;
idx = i - l ;
}
}
return t.substr(idx, max_len);
}

private:
const int ALPHABET = 128;

vector<int> get_sa(const string& s);
vector<int> get_lcp(const string& s, const vector<int>& sa, vector<int>& rank);
};

Share