题解：P10469 后缀数组

· · 题解

思路

求取 \text{SA} 数组，容易想到排序。但是直接比较字符串的字典序将会使排序的时间复杂度达到 \mathcal{O}(n^2 \log n)，超时，考虑优化。

这里用到的技巧是：比较两个字符串的字典序，可以通过哈希 + 二分的优化达到单次询问 \mathcal{O}(\log n)。原理很简单：模拟手动比较字符串字典序的顺序，容易发现以下过程：

  1. 从第一个字符开始比较。

  2. 如果当前字符不相等，就直接比较这两个字符，即可得出答案。

  3. 否则，继续比较下一个字符。

这个过程实际上就是在寻找两个字符串的最长公共前缀，而下一个字符就一定不相等。两个字符串的最长公共前缀如何求取？同 P10479 匹配统计，这是具有单调性的（事实上，你可以在 P10479 里看到我的题解，与下面的描述一样）：如果前 x 个字符串可以匹配，则前 y(y<x) 个字符串也可以匹配；如果前 x 个字符串不可以匹配，则前 y(y>x) 个字符串也不可以匹配。可以通过二分来寻找最大的 x，配合哈希，可以做到 \mathcal{O}(\log n) 的时间复杂度。这样，就可以把排序优化到 \mathcal{O}(n\log^2n) 的时间复杂度了，符合要求。

而 \text{Height} 数组的求取也就易如反掌了：单次哈希 + 二分求最长公共前缀 \mathcal{O}(\log n)，这部分的总时间复杂度为 \mathcal{O}(n\log n)。

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std; 

typedef unsigned long long ull;

const int N = 3e5 + 5, base = 1e9 + 7;

string s;

int n, SA[N], Height[N];

ull hs[N], pw[N];

ull get_hash(int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
}

int find_pos(int x, int y) {
    int l = -1, r = min(n - x + 1, n - y + 1) + 1;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (get_hash(x, x + mid - 1) == get_hash(y, y + mid - 1))
            l = mid;
        else    
            r = mid;
    }
    return l;
}

bool cmp(int x, int y) {
    int pos = find_pos(x, y);
    return s[x + pos] < s[y + pos];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = s.size();
    s = '#' + s;
    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        SA[i] = i;
        pw[i] = pw[i - 1] * base;
        hs[i] = hs[i - 1] * base + s[i];
    }
    sort(SA + 1, SA + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        cout << SA[i] - 1 << " "; // 注意题目中的下标从0开始
    cout << "\n";
    for (int i = 1; i <= n; i++) 
        cout << find_pos(SA[i], SA[i - 1]) << " ";
    return 0;
}