后缀数组
题意
后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者 DC3 算法实现，这超出了我们的讨论范围。
在本题中，我们希望使用快排、Hash 与二分实现一个简单的O(nlog2n) 的后缀数组求法。
详细地说，给定一个长度为 n 的字符串 S（下标 0∼n−1），我们可以用整数 k(0≤k<n) 表示字符串 S 的后缀 S(k∼n−1)。
把字符串 S 的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。
额外地，我们考虑排名为 i 的后缀与排名为 i−1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。
我们的任务就是求出 SA 与 Height 这两个数组。
思路
先求 SA 数组
代码
#include<bits/stdc++.h> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 3e5 + 10; const int base = 131; ULL h[N]; ULL p[N]; int sa[N]; char s[N]; int n; ULL get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int get_max_common_prefix(int a, int b) { int l = 0, r = min(n - a + 1, n - b + 1); while (l < r) { // 二分长度 int mid = l + r + 1 >> 1; if (get_hash(a, a + mid - 1) != get_hash(b, b + mid - 1))r = mid - 1; else l = mid; } return l; } bool cmp(int a, int b) { // 按字典序排序 int l = get_max_common_prefix(a, b); int av = a + l > n ? INT_MIN : s[a + l]; int bv = b + l > n ? INT_MIN : s[b + l]; return av < bv; } void solve() { scanf("%s", s + 1); n = strlen(s + 1); p[0] = 1; for (int i = 1; i <= n; ++i) { p[i] = p[i - 1] * base; h[i] = h[i - 1] * base + s[i]; sa[i] = i; } sort(sa + 1, sa + 1 + n, cmp); for (int i = 1; i <= n; ++i)printf("%d ", sa[i] - 1); printf("\n"); for (int i = 1; i <= n; ++i) { if (i == 1)printf("0 "); else printf("%d ", get_max_common_prefix(sa[i], sa[i - 1])); } } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
