Luobuyu's Blog

0%

1163. 按字典序排在最后的子串

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 3k 阅读时长 ≈ 3 分钟
使用双指针可以巧妙解决，实在不行直接用后缀数组。

1163.按字典序排在最后的子串

题目描述：

给出一个字符串 $s$ ，长度为 $n$ ，找出它的所有子串并按照字典序排列，返回字典序最大的子串。

数据范围： $1\le n \le 4\times 10^5$

题解：

显然，返回的子串是最大的后缀。因为当前缀相等时，更长的字符串字典序更大，因此会选择更长的，也就是后缀。

双指针：

使用双指针 $i,j$ ，指针 $i$ 表示最大的后缀的起始位置， $j$ 为正在和 $i$ 比较的后缀的起始位置。

  • $s[i + k] = s[j + k]$ ： $k$ 继续增加向后移动。
  • $s[i + k] > s[j + k]$ ： $s[i,i + k - 1],s[j,j + k - 1]$ 是完全相等的，说明 $j + p\in [j, j + k]$ 不可能作为最大字符串的起始位置，因为如果位置 $j + p$ 可以取，那么对于 $i$ 来说，位置 $i + p$ 开始的后缀字符串 $s[i + p, i + k - 1], s[j + p, j + k - 1]$ 相等，但是下一个字符 $i$ 的比较大，因此 $j + p$ 不可能作为最大字符串的起始位置。 那么 $j$ 可以直接跳过这一段 $j = j + k + 1$ ，继续从后面比较。
  • $s[i + k] < s[j + k]$ ：同理， $i$ 可以跳过这一段 $i = i + k + 1$ ，如果 $i \ge j$ ，那么需要将 $j$ 移到 $i$ 的后面，即 $j = i + 1$ 。

后缀数组：

后缀数组， $sa$ 数组， $sa[i] = k$ 表示的是第 $i$ 小的后缀字符串的起始位置 $k$ ，即后缀 $s[k:n-1]$ 是第 $i$ 小的后缀字符串，则 $sa[n - 1]$ 则表示最大的后缀的起始位置。所以直接返回 $s.substr(sa[n-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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    string lastSubstring(string s)
    {
        int i = 0, k = 0, n = s.length();
        for (int j = 1; j + k < n;)
        {
            if (s[i + k] == s[j + k])
                ++k;
            else if (s[i + k] > s[j + k])
            {
                j = j + k + 1;
                k = 0;
            }
            else
            {
                i = i + k + 1;
                k = 0;
                if (i >= j)
                    j = i + 1;
            }
        }
        return s.substr(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
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
85
86
87
88
89
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 4e5 + 10;
    int sa[maxn], wa[maxn], wb[maxn], bucket[maxn];
    // wa 第一关键字， wb 第二关键字
    string s;
    int rk[maxn], height[maxn];
    void getHeight(int n)
    {
        int k = 0;
        for (int i = 0; i < n; i++)
            rk[sa[i]] = i + 1; // 之前只得到了sa，还没有搞rk
        for (int i = 0; i < n; i++)
        {
            if (rk[i] == 1)
                continue; // height[1] = 0;
            if (k)
                --k;
            int j = sa[rk[i] - 1];
            while (i + k < n && j + k < n && s[i + k] == s[j + k])
                k++;
            height[rk[i]] = k;
        }
    }
    void getSA(int n, int m = 130)
    {
        int *x = wa, *y = wb;
        for (int i = 0; i <= m; i++)
            bucket[i] = 0; // 桶
        for (int i = 0; i < n; i++)
            bucket[x[i] = s[i] - 'a' + 1]++;
        for (int i = 1; i <= m; i++)
            bucket[i] += bucket[i - 1];
        for (int i = n - 1; i >= 0; i--)
            sa[--bucket[x[i]]] = i;
        // 赋上编号, 排名 获得 编号
        for (int k = 1; k <= n; k <<= 1) // p用来计数最大排名，排名全部不同的时候跳出循环
        {
            int p = 0;
            // y[i] 表示第二关键字排名为i的数，第一关键字的位置
            // 第n-k+1到第n位是没有第二关键字的 所以排名在最前面
            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; // 排名为i的数 在数组中是否在第k位以后
            // 如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进y就行了
            // 所以i枚举的是第二关键字的排名，第二关键字靠前的先入队

            // 按照第二关键字排序
            for (int i = 0; i <= m; i++)
                bucket[i] = 0; // 初始化桶

            for (int i = 0; i < n; i++)
                bucket[x[y[i]]]++;
            for (int i = 1; i <= m; i++)
                bucket[i] += bucket[i - 1];
            for (int i = n - 1; i >= 0; i--)
                sa[--bucket[x[y[i]]]] = y[i]; // 第一关键字相同时，第二关键字，第二关键字较大的这个后缀的排名是啥到了排名，我们也就能更新sa了
                                              // 因为y的顺序是按照第二关键字的顺序来排的
            // 第二关键字靠后的，在同一个第一关键字桶中排名越靠后
            // 基数排序
            swap(x, y);
            x[sa[0]] = 0;
            p = 1;
            for (int i = 1; i < n; i++)
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p - 1 : p++; // 更新排名
            if (p >= n)
                break;
            m = p;
        }
        // 注意最后输出的时候需要输出 sa[i] + 1
        getHeight(n);
    }
    string lastSubstring(string ss)
    {
        s = ss;
        int n = s.length();
        getSA(n, 26);
        return s.substr(sa[n - 1]);
    }
};