算法字符串

后缀数组：排名为i的后缀的起始下标

字数统计: 2.8k字   |   阅读时长: 13分
, , ,

摘要: 后缀数组原理与实现

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

背景

一个长度为 n 的字符串 s，共有 n 种后缀。现在想对这 n 个后缀排序，将排序结果保存在一个数组 sa 中。sa[i] := 排名为 i 的后缀的起始下标。

1
2
3
4
sa[i] := 排名为 i 的后缀的起始下标
rank[i] := 以 s[i] 起始的后缀的排名

rank[sa[i]]=i    sa[rank[i]]=i

模板题: 1163. 按字典序排在最后的子串

给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：
输入：”abab”
输出：”bab”
解释：我们可以找出 7 个子串 [“a”, “ab”, “aba”, “abab”, “b”, “ba”, “bab”]。按字典序排在最后的子串是 “bab”。

示例 2：
输入：”leetcode”
输出：”tcode”

提示：

1
2
1 <= s.length <= 4 * 10^5
s 仅含有小写英文字符。

算法：后缀数组

只要求出 sa，s.substr(sa[n - 1]) 就是答案。难点就在于如何计算 sa，也就是高效地对所有后缀按字典序排序的结果。

基础算法: 对所有后缀快速排序 $O(N^{2}\log N)$

注：超时。

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
class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        vector<int> sa = get_sa(s);
        return s.substr(sa[n - 1]);
    }

private:
    vector<int> get_sa(const string& s)
    {
        int n = s.size();
        vector<int> sa(n);
        vector<int> rank(n);
        vector<pair<string, int>> suffixes;
        for(int i = 0; i < n; ++i)
            suffixes.emplace_back(s.substr(i), i);
        sort(suffixes.begin(), suffixes.end());
        for(int i = 0; i < n; ++i)
        {
            sa[i] = suffixes[i].second;
            rank[suffixes[i].second] = i;
        }
        return sa;
    }
};

下面要在直接快排的算法上进行优化，最终得到后缀数组的算法。

优化1: 倍增法 $O(N\log^{2}N)$

参考: 倍增法。

一共 n 个后缀，首先按照第一个字符(长度为 1)排序。

然后，按照前两个字符(长度为 2)排序。

此后，按照前 len 个字符的排序完成后，利用其排序结果，执行按照前 len * 2 个字符的排序。对于以 s[i] 起始，长度为 len * 2 的这一子串，前半部分 s[i..i+len-1]，后半部分 s[i+len..i+len*2-1] 均为上一轮排序的目标，结果在 rank[i] 和 rank[i+len]。

此时 rank[i] 表示以 s[i] 开始的后缀按照前 len 个字符的排序结果。当 rank 所有名次均不同的时候就可以退出了。

利用长为 len 的两部分对 len * 2 进行排序的过程相当于一个双关键字排序，对于以 s[i] 开头的后缀，本轮排序的第一关键字为 rank[i]，第二关键字为 rank[i + len]。

最后用 rank 后处理出 sa， sa[i] 表示按照前 len 个字符排序名次为 i 的其实下标。

时间复杂度为 $O(N\log^{2}N)$ 其中排序为 $O(N\log N)$，共进行 $O(\log N)$ 轮排序。

其中第一步按第一个字符排序时，用字符计数的方法：

1
2
3
4
在 s 上做一轮字符计数，得到 c
c[s[i]] := 字符 s[i] 的出现次数
再在 c 上本地求一轮前缀和
c[s[i]] 变成了小于等于 s[i] 的字符出现的次数

代码 (C++)

注：$O(N\log^{2}N)$ 超时。

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
class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        vector<int> sa = get_sa(s);
        return s.substr(sa[n]);
    }

private:
    struct Info
    {
        int key1, key2, i;
        Info(){}
        Info(int k1, int k2, int i):key1(k1),key2(k2),i(i){}
    };

    struct Cmp
    {
        bool operator()(const Info& info1, const Info& info2) const
        {
            if(info1.key1 == info2.key1)
                return info1.key2 < info2.key2;
            return info1.key1 < info2.key1;
        }
    };

    bool equal(const Info& info1, const Info& info2) const
    {
        return info1.key1 == info2.key1 && info1.key2 == info2.key2;
    }

    vector<int> get_sa(const string& s)
    {
        vector<int> c(128);
        for(char ch: s) ++c[ch];
        for(int i = 1; i < 128; ++i)
            c[i] += c[i - 1];

        int n = s.size();
        vector<int> rank(n);

        for(int i = 0; i < n; ++i)
            rank[i] = c[s[i]];

        for(int k = 1; k < n; k <<= 1)
        {
            vector<Info> info(n);
            for(int i = 0; i < n; ++i)
            {
                info[i].i = i;
                info[i].key1 = rank[i];
                if(i + k >= n)
                    info[i].key2 = 0;
                else
                    info[i].key2 = rank[i + k];
            }
            sort(info.begin(), info.end(), Cmp());
            int i = 0;
            bool flag = true;
            while(i < n)
            {
                int j = i;
                while(j < n && equal(info[i], info[j]))
                {
                    flag = false;
                    rank[info[j].i] = i + 1;
                    ++j;
                }
                i = j;
            }
            if(flag)
                break;
        }

        vector<int> sa(n + 1);
        for(int i = 0; i < n; ++i)
        {
            sa[rank[i]] = i;
        }

        return sa;
    }
};

优化2: 基数排序

回顾优化1 中，考察在对长度倍增的过程中的某一轮排序过程，利用长为 len 的两部分对 len * 2 进行排序的过程相当于一个双关键字排序，对于以 s[i] 开头的后缀，本轮排序的第一关键字为 rank[i]，第二关键字为 rank[i + len]。

在做这一轮双关键字排序的时候，优化 1 用的是快排，这里换成用基数排序，即对第一关键字和第二关键字分别做一次计数排序。

第二关键字需要一个辅助数组 y, y[i] := 第二关键字排名为 i 的起始下标，rank 里的排名就是第一关键字。

(1) 排所有后缀的长度为 1 的前缀

在进行长度为 1 的排序时，利用排序结果顺便把 sa 也初始化一下，后面迭代过程中第二关键字可以直接从 sa 中得到。

将 rank[i] 放到它在 sa 的正确位置上。对于一个值(第一关键字)来说，c[rank[i]] 的值就是它在 sa 中的位置。在做这步的时候，自减 rank[i]，这样在迭代中就能处理第一关键字的情况了。

1
2
3
4
5
6
7
8
9
for(int i = 0; i < n; ++i)
{
    ++c[s[i]];
   rank[i] = s[i];
}
for(int i = 1; i < ALPHABET; ++i)
    c[i] += c[i - 1];
for(int i = n - 1; i >= 0; --i)
    sa[--c[rank[i]]] = i;

(2) 当长度 k 的处理完，在处理 k * 2 时，首先求第二关键字

此时长度 k 的关键字有序了，可以通过 sa 得到第二关键字

  • 首先看前面的 k 个，前面留了 k 个空位是长度小于等于 k 的后缀，它们没有后半部分，直接将第二关键字赋值为其长度减一(0~k-1)
  • 然后是 n - k 个长度大于 k 的后缀，它们的第二关键字从 k 开始赋值直到 n - 1。从 sa 得到下标后需要减k。
1
2
3
4
5
6
int p = 0;
for(int i = n - k; i < n; ++i)
    y[p++] = i;
for(int i = 0; i < n; ++i)
    if(sa[i] >= k)
        y[p++] = sa[i] - k;

(3) 处理 k * 2 时，做用基数排序做双关键字排序

rank 里是第一关键字排序，rank[i] := 起始下标 i 的第一关键字

sa[--c[rank[y[i]]]] = y[i]; 这个过程，先单独对第二关键字排序，然后由第二关键字顺序改变第一关键字的顺序(rank和c都持有第一关键字信息)，当第一关键字相同时按第二关键字来排序，y[i] := 排名为 i 的第二关键字的起始下标

基数排序的过程就是先对低位排，然后在排高位的时候，高位如果相同，自然是按照低位排的 。

参考 : 非比较排序

1
2
3
4
5
6
7
c.assign(ALPHABET, 0);
for(int i = 0; i < n; ++i)
    ++c[rank[i]];
for(int i = 1; i < ALPHABET; ++i)
    c[i] += c[i - 1];
for(int i = n - 1; i >= 0; --i)
    sa[--c[rank[y[i]]]] = y[i];

(4) 利用 sa 更新 rank

合并关键字的时候判断一下合并以后的关键字是否相同，如果相同，要给相同的 rank。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
rank.swap(y);
p = 1; // 分配的关键字
rank[sa[0]] = 0;
for(int i = 1; i < n; ++i)
{
    // 此时 y 持有的是长为 len 的第一关键字
    // 长为 len 的第二关键字从 sa 获得
    // 合并后的长为 len * 2 的第一关键字放在 rank
    if(y[sa[i - 1]] == y[sa[i]] &&
            (sa[i - 1] + k >= n ? -1 : y[sa[i - 1] + k]) == (sa[i] + k >= n ? -1 : y[sa[i] + k]))
        rank[sa[i]] = p - 1;
    else
    {
        rank[sa[i]] = p;
        p++;
    }
}

代码(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
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
class Solution {
public:
    string lastSubstring(string s) {
        int n = s.size();
        vector<int> sa = get_sa(s);
        return s.substr(sa[n - 1]);
    }

private:
    const int ALPHABET = 128;

    vector<int> get_sa(const string& s)
    {
        vector<int> c(ALPHABET);
        int n = s.size();
        vector<int> rank(n); // 第一关键字
        vector<int> y(n); // 第二关键字
        vector<int> sa(n);

        for(int i = 0; i < n; ++i)
        {
            ++c[s[i]];
            rank[i] = s[i];
        }
        for(int i = 1; i < ALPHABET; ++i)
            c[i] += c[i - 1];
        for(int i = n - 1; i >= 0; --i)
        {
            sa[--c[rank[i]]] = i;
        }

        int m = ALPHABET; // 关键字种类数
        for(int k = 1; k <= n; k <<= 1)
        {
            int p = 0;
            for(int i = n - k; i < n; ++i)
                y[p++] = i;
            for(int i = 0; i < n; ++i)
                if(sa[i] >= k)
                    y[p++] = sa[i] - k;

            c.assign(m, 0);
            for(int i = 0; i < n; ++i)
                ++c[rank[i]];
            for(int i = 1; i < m; ++i)
                c[i] += c[i - 1];
            for(int i = n - 1; i >= 0; --i)
                sa[--c[rank[y[i]]]] = y[i];

            rank.swap(y);
            p = 1; // 分配的关键字
            rank[sa[0]] = 0;
            for(int i = 1; i < n; ++i)
            {
                // 此时 y 持有的是长为 len 的第一关键字
                // 长为 len 的第二关键字从 sa 获得
                // 合并后的长为 len * 2 的第一关键字放在 rank
                if(y[sa[i - 1]] == y[sa[i]] &&
                        (sa[i - 1] + k >= n ? -1 : y[sa[i - 1] + k]) == (sa[i] + k >= n ? -1 : y[sa[i] + k]))
                    rank[sa[i]] = p - 1;
                else
                {
                    rank[sa[i]] = p;
                    p++;
                }
            }

            // 下一轮的关键字种类数
            if(p >= n)
                break;
            m = p;
        }

        return sa;
    }
};

基于后缀数组的字符串匹配

已经计算好 s 的后缀数组 sa。现在要求 t 在 s 中出现的位置。可以通过二分在 $O(M\log N)$ 完成。当 N 很大的时候比 $O(M+N)$ 的方法高效。

因此如果要对 s 做多次匹配(在一个长串中多次找不同的模式，而不是用一个模式多次找不同的长串)，可以用这种算法。

代码(C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> match(string_view s, vector<int>& sa, string_view p)
{
   int n = s.size(), m = p.size();
   int left = 0, right = n - 1;
   while(left < right)
   {
       int mid = (left + right) / 2;
       // 比较 s 从 sa[mid] 开始长度为 m 的子串与 p
       if(s.substr(sa[mid], min(m, n - sa[mid])) < p)
           left = mid + 1;
       else
           right = mid;
   }
   vector<int> result;
   while(left < n && s.substr(sa[left], min(m, n - sa[left])) == p)
   {
       result.push_back(sa[left]);
       ++left;
   }
   return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int strStr(string s, string p) {
        if(p.empty()) return 0;
        if(s.empty()) return -1;
        vector<int> sa = get_sa(s);
        vector<int> matches = match(s, sa, p);
        if(matches.empty()) return -1;
        return *min_element(matches.begin(), matches.end());
    }
private:
    const int ALPHABET = 128;

    vector<int> get_sa(const string& s);
    vector<int> match(string_view s, vector<int>& sa, string_view p);
};
Share