终于来到大名鼎鼎的后缀结构了，后缀结果可以解决许多子串问题。后缀结果是字符串经常考察的点，需要重点学习。
SA
后缀排序，是指这个对字符串\(s\)的每一个后缀字符串进行排序，通过处理每个后缀的前缀来解决子串问题。\(SA\)：排名为\(i\)对应原字符串下标，\(rk\)：下标为\(i\)的后缀排名。
后缀数组，可以根据基数排序在\(O(nlogn)\)的时间复杂度内求出。当然还有更优秀的\(SA-IS\)算法，可以在\(O(n)\)复杂度实现。本文在这里不做介绍，感兴趣的读者可以自行检索。
求出\(SA\)数组后，可以在\(O(n)\)的时间复杂度内求出\(height\)数组，\(height[i]\)表示排名为\(i\)和\(i-1\)的后缀的LCP。而下标\(i,j\)的LCP就是它们排名之间的\(height\)数组最小值，所以我们只需要实现RMQ，就可以快速求出任意的LCP了。感性理解即可。
struct Sa { //俩字符串连一起记得开俩倍空间
char s[MAXN];
int SA[MAXN], rk[MAXN], oldrk[MAXN << 1], id[MAXN], key1[MAXN], cnt[MAXN]; //SA排名为i对应原字符串下标，rk下标为i的后缀排名
int height[MAXN], n; //height与上一个排名相同的个数，height[1]=0
inline bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
inline void getSA() {
memset(cnt, 0, sizeof(cnt));
memset(rk, 0, sizeof(rk));
n = strlen(s + 1);
int m = 127;
for (int i = 1; i <= n; ++i)++cnt[rk[i] = s[i]];
for (int i = 1; i <= m; ++i)cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i)SA[cnt[rk[i]]--] = i;
for (int len = 1, p;; len <<= 1, m = p) {
p = 0;
for (int i = n; i > n - len; --i)id[++p] = i;
for (int i = 1; i <= n; ++i)
if (SA[i] > len)id[++p] = SA[i] - len;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; ++i)++cnt[key1[i] = rk[id[i]]];
for (int i = 1; i <= m; ++i)cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i)SA[cnt[key1[i]]--] = id[i];
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
p = 0;
for (int i = 1; i <= n; ++i)
rk[SA[i]] = cmp(SA[i], SA[i - 1], len) ? p : ++p;
if (p == n)break;
}
// for (int i = 1; i <= n; ++i)printf("%d ", SA[i]); printf("\n");
// for (int i = 1; i <= n; ++i)printf("%d ", rk[i]); printf("\n");
}
inline void getHeight() {
for (int i = 1, k = 0; i <= n; ++i) {
if (rk[i] == 0)continue;
if (k)--k;
while (s[i + k] == s[SA[rk[i] - 1] + k])++k;
height[rk[i]] = k;
}
}
int st[MAXN][LOG], lg[MAXN];
inline void initST() {
lg[1] = 0;
for (int i = 2; i <= n; i++)lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++)st[i][0] = height[i];
for (int j = 1; j <= lg[n]; j++)
for (int i = 1; i <= n - (1 << j) + 1; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
inline int RMQ(int x, int y) {
int t = lg[y - x + 1];
return min(st[x][t], st[y - (1 << t) + 1][t]);
}
inline int LCP(int x, int y) {
x = rk[x], y = rk[y];
if (x > y)swap(x, y);
return RMQ(x + 1, y);
}
};
技巧：
- 翻转字符串
求出的后缀变成前缀，lcp变成lsp - 重复字符串
解决循环问题 - 拼接字符串
在两个字符串之间用#等没有出现过的字符连接，就可以处理多字符串问题
应用
-
最长公共前缀
给定一个字符串，询问某两个后缀的最长公共前缀。
求区间rmq即可。 -
可重叠最长重复子串
重复子串：字符串 \(R\) 在字符串 \(L\) 中至少出现两次，则称 \(R\) 是 \(L\) 的重复子串。
给定一个字符串，求最长重复子串，这两个子串可以重叠。
求最大\(height\)即可。 -
不可重叠最长重复子串
二分答案判断即可。 -
可重叠k次的最长重复子串
给定一个字符串，求至少出现 \(k\) 次的最长重复子串，这 \(k\) 个子串可以重叠。
二分答案，判断可通过二分得知和这个子串相同前缀大于\(mid\)的字符串有多少。 -
不同子串个数（后缀的前缀
给定一个字符串，求不相同的子串的个数。
考虑一个新的\(rk\)字符串新加入了多少之前没出现过的子串，就是这个字符串的长度-\(height\) -
连续重复子串
给定一个字符串 \(L\)，已知这个字符串是由某个字符串 \(S\) 重复 \(R\) 次而得到的，求 \(R\) 的最大值
通过\(z\)函数求\(LCP\)，可快速算出。\(SA\)通过类似的方式求\(LCP\)即可。 -
连续次数最多的重复子串
枚举重复子串长度\(L\)，因为至少两次重复必定跨越枚举的长点的两点。每次增加\(L\)即可。复杂度调和级数。通过\(LCP\)和\(LCS\)求得最多次数。 -
最小表示
把原串重复拼起来，找最小的，起点小于\(|S|\)的\(rk\)即可。 -
最长公共子串
两个字符串的相关问题
合并两字符串，求最大\(height\)即可。 -
长度不小于 \(k\) 的公共子串的个数
对于\(S\)串，\(rk\)排名处做一个前缀和的标记，每次遇到\(T\)串，进行二分。找到长度不小于 \(k\) 的区间。前缀和求出这个区间有多少，是\(S\)串的即可。
oiwiki上介绍了许多SA和其他算法的结合，也给出了许多例题，可以参考。
例题：
SAM
后缀自动机，通过构造一种DAG（有向无环图），求出这个字符串的所有子串。从原点到达的任意点，途径的边权构成的字符串就是一个子串。可以证明SAM最多构建\(2n-1\)个点和\(3n-4\)条边。
一些概念
-
endpos: \(s\)中同一结束位置的字符串集合。（前缀的后缀）
SAM中每一个点都是一个endpos。因为每个点的结束位置都不同，所以对应于原字符串\(s\)都是唯一的子串。 -
longest: endpos中最长元素的长度。记为\(len\)
每一个endpos最长的可能就是从起始位置开始的元素 -
link: 后缀链接，连接到对应\(w\)的最长后缀的另一个endpos等价类。
link构成一个树形结构。这棵树的父亲和儿子有相同的后缀。这个点endpos包含的的元素等于\(len[u]-len[fa[u]]\)。任意子树，都含有这个子树根所包含的元素为后缀。
每个状态s代表的所有串在原串中的出现次数及每次出现的右端点相同。
在树中，每个状态的集合是它的父状态集合的子集。
两个串的LCS，位于这两个串对应的状态在树上的最近公共祖先状态
struct SAM { //最多2n-1个点和3n-4条边
int len[MAXN << 1], link[MAXN << 1], ch[MAXN << 1][26]; //我们记 longest(v) 为其中最长的一个字符串，记 len(v) 为它的长度。
int cnt[MAXN << 1];
int cur, lst, siz;
SAM() { clear(); }
void clear() { //设置起始点S
memset(ch, 0, sizeof(int) * (siz + 1) * 26);
len[0] = 0;
link[0] = -1;
siz = 0; //siz设置成0实际上有一个点，方便标记
lst = cur = 0;
}
void extend(int c) {
lst = cur, cur = ++siz;
len[cur] = len[lst] + 1;
cnt[cur] = 1;
for (; ~lst && !ch[lst][c]; lst = link[lst])ch[lst][c] = cur;
if (lst == -1) {
link[cur] = 0;
} else {
int q = ch[lst][c];
if (len[lst] + 1 == len[q]) {
link[cur] = q;
} else { //克隆的点是q(lst的c后继)
int clone = ++siz;
link[clone] = link[q];
len[clone] = len[lst] + 1;
link[cur] = link[q] = clone;
for (; ~lst && ch[lst][c] == q; lst = link[lst])ch[lst][c] = clone;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
}
}
}
};
应用
-
最长公共子串
对\(S\)建立SAM，\(T\)在\(S\)上跑。每个状态最长匹配长度取min，所有状态取max即可。 -
字典序k小子串
对SAM跑一边拓扑排序，然后按照大小跑一边dfs即可 -
最小表示
对\(S + S\)构建SAM，每次走最小的转移，走\(|S|\)次就是最小表示。 -
给一个长度为n的字符串，求它的所有后缀两两的最长公共前缀长度之和。
考虑每个点成为LCA的次数，即它的endpos数量。\(len[u] * cnt[u]\)。 -
第一次出现的位置
考虑找到最小\(len\)
其余的可以参考oiwiki
SAM问题经常转化为树上问题，比如LCA，树链剖分，dsu on tree，线段树合并等。
例题：
The 2023 ICPC Asia EC Regionals Online Contest (I)
CF:235 C. Cyclical Quest
广义后缀自动机
用SAM解决多模式串问题，即在trie上构建SAM。
洛谷题解解释的非常详细，可以供参考。
这里引用其中的一些内容：
在用广义\(SAM\)处理多模式串问题时，网上流传着的主流写法有3种：
（1）.用特殊符号将所有模式串连成一个大串放到一个\(SAM\)中，再加一些玄学判断来处理信息。
（2）.每次插入一个模式串之前，都把\(last\)设为\(1\)，按照普通\(SAM\)一样插入，即每个字符串都从起点\(1\)开始重新构造。
（3）.用所有模式串建出一颗\(Trie\)树，对其进行\(dfs/bfs\)遍历构建\(SAM\)，\(insert\)时使\(last\)为它在\(Trie\)树上的父亲，其余和普通\(SAM\)一样。
第一种实用性不高且复杂度危险。第二种机房大佬说是盗版，但因为复杂度依旧为线性、代码简单且在大部分题中都能保证正确性，所以很多人都用的这种（\(SAM Drawer\)似乎就是依据这个做法绘的图）。但根据广义\(SAM\)的定义，只有第三种中才是正确写法。而且随便抛组数据就能立马发现构造出来的差异。
离线做法即在\(Trie\)上遍历插入到\(SAM\)中。
struct Trie {
int nxt[MAXN << 1][26];
int tot;
Trie() { init(); }
void init() { tot = 0; }
int insert(int cur, int c) {
if (nxt[cur][c])return nxt[cur][c];
return nxt[cur][c] = ++tot;
}
void buildTrie(const char* s, int len) {
int root = 0;
for (int i = 1; i <= len; ++i)
root = insert(root, s[i] - 'a');
}
};
struct exSAM :Trie { //最多2n-1个点和3n-4条边
int len[MAXN << 1], link[MAXN << 1]; //我们记 longest(v) 为其中最长的一个字符串，记 len(v) 为它的长度。
exSAM() { clear(); }
void clear() { //设置起始点S
len[0] = 0;
link[0] = -1;
}
int extend(int lst, int c) {
int cur = nxt[lst][c];
if (len[cur])return cur;
len[cur] = len[lst] + 1;
int p = link[lst];
for (; ~p && !nxt[p][c]; p = link[p])nxt[p][c] = cur;
if (p == -1) {
link[cur] = 0;
} else {
int q = nxt[p][c];
if (len[p] + 1 == len[q]) {
link[cur] = q;
} else { //克隆的点是q(p的c后继)
int clone = ++tot;
for (int i = 0; i < 26; ++i)
nxt[clone][i] = len[nxt[q][i]] != 0 ? nxt[q][i] : 0;
link[clone] = link[q];
len[clone] = len[p] + 1;
link[cur] = link[q] = clone;
for (; ~p && nxt[p][c] == q; p = link[p])nxt[p][c] = clone;
}
}
return cur;
}
void buildexSAM() {
queue<pii>que;
for (int i = 0; i < 26; ++i)
if (nxt[0][i])que.push({ i,0 });
while (!que.empty()) {
auto item = que.front();
que.pop();
auto lst = extend(item.second, item.first);
for (int i = 0; i < 26; ++i)
if (nxt[lst][i])
que.push({ i,lst });
}
}
};
在线做法就是在方法二的基础上加入特判。
struct SAM { //最多2n-1个点和3n-4条边
int len[MAXN << 1], link[MAXN << 1], ch[MAXN << 1][26]; //我们记 longest(v) 为其中最长的一个字符串，记 len(v) 为它的长度。
int cnt[MAXN << 1];
int cur, lst, siz;
SAM() { clear(); }
void clear() { //设置起始点S
memset(ch, 0, sizeof(int) * (siz + 1) * 26);
len[0] = 0;
link[0] = -1;
siz = 0; //siz设置成0实际上有一个点，方便标记
lst = cur = 0;
}
void extend(int c) {
lst = cur;
if (ch[lst][c]) {
int q = ch[lst][c];
if (len[lst] + 1 == len[q])return cur = q, void();
else {
int clone = ++siz;
link[clone] = link[q];
len[clone] = len[lst] + 1;
link[q] = clone;
for (; ~lst && ch[lst][c] == q; lst = link[lst])ch[lst][c] = clone;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
return cur = clone, void();
}
}
cur = ++siz;
len[cur] = len[lst] + 1;
cnt[cur] = 1;
for (; ~lst && !ch[lst][c]; lst = link[lst])ch[lst][c] = cur;
if (lst == -1) {
link[cur] = 0;
} else {
int q = ch[lst][c];
if (len[lst] + 1 == len[q]) {
link[cur] = q;
} else { //克隆的点是q(lst的c后继)
int clone = ++siz;
link[clone] = link[q];
len[clone] = len[lst] + 1;
link[cur] = link[q] = clone;
for (; ~lst && ch[lst][c] == q; lst = link[lst])ch[lst][c] = clone;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
}
}
}
};