目录
后缀数组是一种非常强大的一种处理字符串问题的工具
后缀数组简介
前置知识：计数排序、基数排序
后缀数组（Suffix Array）主要关系到两个数组：sa和rk
-
\(sa[i]\) ：表示将所有后缀排序后第 \(i\) 小的后缀的编号 （也就是后缀数组）；
- 编号也就是其实下标，例如\(a\ b\ c\ d\ e\)中，\(cde\)的编号即是\(2\)（开始下标）
-
$ rk[i] $ ：表示编号为 \(i\) 的后缀的排名，是重要的辅助数组；
此外还有一个 \(lc\) 数组
- \(lc[i]\) ：\(lc[i]\) 其实是 \(height[i]\ =\ lcp(i, j)\)，即第 \(i\) 名后缀与第 \(i - 1\) 名的后缀的最长公共前缀
- 后续会介绍它
后缀数组可以用于什么场景
单纯的后缀数组 \(sa\) ：
- 寻找最小的循环移动位置
- 在字符串中寻找子串
- 给你一个字符串，每次从首或尾取一个字符组成字符串，问所有能够组成的字符串中字典序最小的一个
最长公共前缀 \(height\)：
- 两子串最长公共前缀
- 比较一个字符串两个子串的大小关系
- 不同子串的数目
- 出现至少 k 次的子串的最大长度
- 是否有某字符串在文本串中至少不重叠地出现了两次
- 连续的若干相同子串
如何实现后缀数组
实现后缀数组有两种方法：
- 倍增法 \(O(nlogn)\)
- DC3法 \(O(n)\)
因为优化后的倍增法常数小，时间复杂度 \(O(nlogn)\) 也是完全够用的，以后有时间会写一下DC3法
倍增法求后缀数组
如果按照暴力的解法，就是将每个后缀丢进数组中直接sort即可，但是太慢了；
我们可以通过倍增的思想，使用基数排序（多关键字排序）
如果按照原生基数排序：
// 对第二关键字：id[i] + w进行计数排序
memset(cnt, 0, sizeof(cnt));
memcpy(id + 1, sa + 1, n * sizeof(int)); // id保存一份儿sa的拷贝，实质上就相当于oldsa
for (i = 1; i <= n; ++i) ++cnt[rk[id[i] + w]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[id[i] + w]]--] = id[i];
// 对第一关键字：id[i]进行计数排序
// 当第一关键字的值相同时，原先排在后面的数还排在后面
memset(cnt, 0, sizeof(cnt));
memcpy(id + 1, sa + 1, n * sizeof(int));
for (i = 1; i <= n; ++i) ++cnt[rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[id[i]]]--] = id[i];
这样常数很大
思考一下第二关键字排序的实质，其实就是把超出字符串范围（即\(sa[i]\ +\ w\ >\ n\)）的 \(sa[i]\) 放到 \(sa\) 数组头部，剩下的依照原顺序放入，没必要计数排序一次。
//tmp存第二关键字序
for (int i = 0; i < k; ++i)
tmp.push_back(n - k + i);
for (auto i : sa)
if (i >= k)
tmp.push_back(i - k);
然后依据 \(tmp\) 对第一关键字计数排序就可以了
std::fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; ++i)
++cnt[rk[i]];
for (int i = 1; i < n; ++i)
cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i)
sa[--cnt[rk[tmp[i]]]] = tmp[i];
然后依据计算出的 \(sa\) 数组，求出对应的 \(rk\) 即可
直接从前到后遍历 \(sa\)
- 若 \(sa[i]\) 从前的排名就比 \(sa[i\ -\ 1]\) 大，现在加上第二关键字亦然
- 若 \(sa[i\ -\ 1]\ +\ k\ ==\ n\)，说明 \(sa[i]\) 不可能和 \(sa[i - 1]\) 一样大
- 若 \(sa[i]\) 的第二关键字比 \(sa[i\ -\ 1]\) 的第二关键字大
以上情况都是 \(sa[i]\) 比 \(sa[i\ -\ 1]\) 大的情况，这种时候 \(sa[i]\) 的
rank必然比 \(sa[i-1]\) 的rank多一
//将原来的rk放入tmp中
std::swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
如果 \(rk[n\ -\ 1]\ >=\ n\ -\ 1\) 了，则说明可以不用再继续排序了
因为这种时候，已经没有两个字典序的一样的串了，就没有必要再继续下去了
参照代码讲解一下：
struct SuffixArray {
int n;
//sa[i]：排名第i的后缀的开始下标
//rk[i]：开始下标为i的后缀的排名
//lc[i]：height数组
std::vector<int> sa, rk, lc;
SuffixArray(const std::string &s) {
n = s.length();
sa.resize(n);
lc.resize(n - 1);
rk.resize(n);
//从0开始递增赋值
std::iota(sa.begin(), sa.end(), 0);
//长度为1的情况，直接根据字符串大小对sa排序
std::sort(sa.begin(), sa.end(), [&](int a, int b) {return s[a] < s[b];});
//由sa算出rk数组
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)//如果sa[i]!=sa[i-1]，sa[i]必然比sa[i-1]大，
//这时候排名要比前一个多1
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
int k = 1;
std::vector<int> tmp, cnt(n);
tmp.reserve(n);
//当rk[sa[n-1]]==n-1的时候代表排序完成
//或者当前长度已经全都不相同了，就没必要继续了
while (rk[sa[n - 1]] < n - 1) {
tmp.clear();
//优化了对第二关键字的计数排序，tmp[i]记录的是排名为i的[[长度为2k的后缀]的第二关键字起始位置]
for (int i = 0; i < k; ++i)
tmp.push_back(n - k + i);
for (auto i : sa)
if (i >= k)
tmp.push_back(i - k);
std::fill(cnt.begin(), cnt.end(), 0);
//对第一关键字计数排序，tmp靠后的在sa中也靠后
for (int i = 0; i < n; ++i)
++cnt[rk[i]];
for (int i = 1; i < n; ++i)
cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i)
sa[--cnt[rk[tmp[i]]]] = tmp[i];
std::swap(rk, tmp);
//根据sa求出rk，上面详解过这里
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i -
1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
//倍增
k *= 2;
}
//这里求height数组
for (int i = 0, j = 0; i < n; ++i) {
if (rk[i] == 0) {
j = 0;
} else {
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] ==
s[sa[rk[i] - 1] + j]; )
++j;
lc[rk[i] - 1] = j;
}
}
}
};
\(height\) 数组
\(LCP\) （最长公共前缀）
\(lcp(x,\ y)\) ：字符串 \(x\) 与字符串 y 的最长公共前缀，在这里指的是 x 号后缀与 y 号后缀的最长公共前缀
\(height\)
\(height[i]\)：\(lcp(sa[i],sa[i - 1])\)，即排名为 \(i\) 的后缀与排名为 \(i\ -\ 1\) 的后缀的最长公共前缀
//这里求height数组
for (int i = 0, j = 0; i < n; ++i) {
if (rk[i] == 0) {
j = 0;
} else {
//就判断sa[i]开始和sa[rk[i] - 1]开始的最长公共前缀能到哪
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] ==
s[sa[rk[i] - 1] + j]; )
++j;
//lc即是height
lc[rk[i] - 1] = j;
}
}
代码模板
struct SuffixArray {
int n;
std::vector<int> sa, rk, lc;
SuffixArray(const std::string &s) {
n = s.length();
sa.resize(n);
lc.resize(n - 1);
rk.resize(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int a, int b) {return s[a] < s[b];});
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
int k = 1;
std::vector<int> tmp, cnt(n);
tmp.reserve(n);
while (rk[sa[n - 1]] < n - 1) {
tmp.clear();
for (int i = 0; i < k; ++i)
tmp.push_back(n - k + i);
for (auto i : sa)
if (i >= k)
tmp.push_back(i - k);
std::fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; ++i)
++cnt[rk[i]];
for (int i = 1; i < n; ++i)
cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i)
sa[--cnt[rk[tmp[i]]]] = tmp[i];
std::swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i -
1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
k *= 2;
}
for (int i = 0, j = 0; i < n; ++i) {
if (rk[i] == 0) {
j = 0;
} else {
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] ==
s[sa[rk[i] - 1] + j]; )
++j;
lc[rk[i] - 1] = j;
}
}
}
};
参考文章
后缀数组简介 - OI Wiki (oi-wiki.org)
模板来自【jiangly】算法模板，群里有
标签：tmp,cnt,后缀,int,jiangly,sa,模板,rk From： https://www.cnblogs.com/xiwen-ydys/p/18299719