前文(SAM 基础)
如果你并不是很熟 SAM,可以看看我远古时期的 blog:浅析后缀自动机 - -Wallace- - 博客园 (cnblogs.com)
缘起
为什么突然想到这个方面的东西,是因为在 ZJU 校队预组队时做到一个 CF-GYM-100418C,当时一眼 SA 但实际上根本不熟。赛后发现有位国外老哥随手 SAM 暴打,一点都不麻烦。
所以本来打算学学 SA,现在又改了主意。大多数观点认为字典序相关问题中 SA 常常占优势,现在我就来正经地来补一补 SAM 的这个短板。
并不是说 SA \(\subset\) SAM,这两者不能互相替代,比如 SAM 就有一个空间问题。不学 SA 只是我懒。
引入:后缀排序
首先对 \(s\) 的 反串 \(s^R\) 建立 SAM,得到的 parent tree 就是后缀树。
所谓后缀树,就是所有 \(s\) 的后缀插入到 Trie 中所得。这里通过将一段没有分支的长链压缩为单条边实现了 \(O(n)\) 复杂度。
考虑一个显而易见的事实:如果将每个点的出边按字典序排好,然后按序 dfs,得到的后缀就是有序的。现在主要的问题就是:如何求出每一条树上出边的 第一个字符。
考虑还原到 \(s\) 串上。我们建立了反串 SAM,就维护出 \(s^R\) 上的 \(\text{endpos}\) 集合(也即 \(s\) 的 \(\text{startpos}\))中的 第一个元素。
对于一个 \(f = link(x)\),从 \(f\) 到 \(x\) 的 \(\text{endpos}\) 发生改变,原因是在 \(maxlen(x)\) 后面一个出现不一样导致 \(\text{endpos}(f)\) 中的元素分家。这个第一个出现不一样的就在 \(s^R[\text{endpos}(x)_{any}-len(f)]\) 处。
那就好办,建 parent tree 的时候就记下这个字符,然后对每个点排序所有出边。
最后就是怎么判断是不是包含后缀的结点。如果包含后缀,当且仅当在 \(s^R\) 上 \(\min\limits_{i \in \text{endpos}(x)} i = len(x)\)。该等价类中最长的已经到头,而到头就意味着 \(s^R\) 的前缀也就是 \(s\) 的后缀。
不要忘了将 \(s^R\) 还原为 \(s\) 上的下标。
参考代码(由于空间缘故只能过 LOJ 模板):
#include <bits/stdc++.h>
#define link other_link
const int N = 1e6 + 5;
const int S = 62;
int ch[N * 2][S], link[N * 2], len[N * 2], right[N * 2];
int total = 1, last = 1;
void extend(int c, int pos) {
int p = last, np = last = ++total;
len[np] = len[p] + 1, right[np] = pos;
for (; p && !ch[p][c]; p = link[p]) ch[p][c] = np;
if (!p) { link[np] = 1; return; }
int q = ch[p][c];
if (len[q] == len[p] + 1) { link[np] = q; return; }
int nq = ++total;
memcpy(ch[nq], ch[q], S << 2);
link[nq] = link[q], right[nq] = right[q];
len[nq] = len[p] + 1, link[np] = link[q] = nq;
for (; p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}
char s[N];
int n;
std::vector<std::pair<char, int>> adj[N * 2];
std::vector<int> ans;
void dfs(int x) {
if (x != 1 && right[x] == len[x])
ans.push_back(n - right[x] + 1);
for (auto [c, y] : adj[x])
dfs(y);
}
int ord(char x) {
if (isdigit(x)) return x - '0';
else if (isupper(x)) return x - 'A' + 10;
else return x - 'a' + 36;
}
signed main() {
scanf("%s", s + 1);
n = strlen(s + 1);
std::reverse(s + 1, s + 1 + n);
for (int i = 1; i <= n; i++)
extend(ord(s[i]), i);
for (int i = 2; i <= total; i++) {
int x = i;
int f = link[x];
char c = s[right[x] - len[f]];
adj[f].emplace_back(c, x);
}
for (int i = 1; i <= total; i++)
std::sort(adj[i].begin(), adj[i].end());
dfs(1);
for (auto x : ans)
printf("%d ", x);
puts("");
return 0;
}
关于反串 \(s^R\)
为什么要反转?
考虑正串 \(s\) 上的字典序是从左到右,而直接对 \(s\) 建 SAM 得到的是“后缀链接 \(link\)”。
我们要的是“前缀链接”,每次上跳一个前缀,即在前缀相同的情况下向下跳实现向后的追加——这和字典序比较的过程时近乎相同的。
于是反转 \(s\),对 \(s^R\) 建 SAM,得到的就是前缀链接而非后缀链接,得到的是 \(startpos\) 而非 \(endpos\)。
例题
【CFGYM-100418C】Substrings
题意
给定一个串 \(s\),\(q\) 次询问,每次问 \(s\) 的所有子串中字典序小于 \(s[l,r]\) 的个数。
题解
如上文,按字典序建的 \(s^R\) 的 parent tree 完成后,等价类中的所有串的排名(\(s\) 所有子串的字典序排名)一定连续。
联系到 Trie 的知识可知,按字典序 dfs 得到的 dfs 序(dfn)就是这些等价类的排名。实际上也就能理解为是所有子串的排名。
对于一个 \(s[l, r]\),我们用家喻户晓的倍增法定位到其所属的等价类中,然后所有满足 dfn 在该等价类(即该结点)之前的结点都是字典序在其之前的点都是字典序小于 \(s[l, r]\) 的。
一个在 dfn 上的前缀和就能搞定。对于自己这个等价类也是只要看看有多少比自己小的串即可。
时间瓶颈在倍增,复杂度 \(O(|s|+q\log |s|)\)。
【LOJ2102】「TJOI2015」弦论
题意
求 \(s\) 所有子串中字典序升序 \(k-\text{th}\) 的子串。分是否考虑本质不同两种。
题解
有一个 DAG 上走的算法这里不赘述。
考虑按字典序建的 \(s^R\) 的 parent tree 上 dfs,每次走到一个点就将 \(k\) 减去该点所代表的串的数量(分两种情况),直到不够减(此时剩下的为 \(k'\)),说明这个结点(\(x\))就含有所求的答案:
如果要求本质不同,长度为 \(len(link(x)) + k'\) 的串就是所求。
如果重复计算本质不同,长度为 \(len(link(x)) + \left\lceil\dfrac{k}{|\text{endpos(x)}|}\right\rceil\) 的即为所求。
结语
如上,一些基本的字典序 & 子串的题目 SAM 是可以胜任的,或者说其实是背后的那个后缀树在起主要作用。
DAG 的作用在逐渐被替代,但也没有完全替代我也不好说。
标签:SAM,int,len,后缀,link,解法,字典 From: https://www.cnblogs.com/Lice-wx/p/lexico-sam.html