自动搬运

查看原文

来自洛谷，原作者为

	Weekoder **

搬运于2025-08-24 22:58:15，当前版本为作者最后更新于2024-06-14 21:47:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

求取 $\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;
}