算法字符串

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

字数统计: 1.9k字   |   阅读时长: 8分
, ,

摘要: 高度数组

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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