后缀自动机
很毒瘤的字符串数据结构，但是我觉得多在脑子里梳理几遍后，比后缀数组好用多了（
这里跳过几乎所有证明，除了对后面理解有影响的，因为我认为这些不重要也学不会
主要记录对做题有帮助的核心性质
字符串的 SAM 可以理解为这个字符串的所有子串的压缩形式
定义
SAM 是一个接受且仅接受字符串的所有后缀的最小 DFA
-
SAM 是 DAG，状态为节点，边上有字母，为转移
-
\(root\) 为初始节点，构建时当前代表整个串的末尾节点为终止节点（在最终，\(root\) 走到它们代表原串的前缀）
-
从一个节点出发的所有转移不同，从初始状态出发走到终止状态，形成的字符串与原串的每个子串一一对应
-
可能到达某状态的路径不止一条，所以一个节点其实代表了某些字符串的集合（后面会具体说明是哪些）
endpos 集合
这是后缀自动机的关键之处
字符串的子串个数是 \(O(n^2)\) 的，它为什么只有 \(O(n)\) 个状态和转移？
定义
\(endpos(t)\)：对于某个子串 \(t\)，它在原串 \(s\) 中出现位置的右端点的集合
举个例子，\(ababac\) 中，\(endpos(ab)=\{2,4\},endpos(abac)=\{6\}\)
这样所有的子串都能根据 \(endpos\) 划分为若干等价类，特别的，\(endpos(root)=\{1,2,\dots n\}\)
性质
-
如果 \(endpos(u)=endpos(v)\)，则其中一个必然为另一个的后缀
证明显然，反证法即可，感性理解更容易（
-
\(endpos(u)\) 与 \(endpos(v)\) 只有两种关系： \(endpos(u)\subseteq endpos(v)\) 或 \(endpos(u)\cap endpos(v)=\varnothing\)
为 1 的逆命题，这为 parent tree 的建造打下了基础
-
将同一 \(endpos\) 等价类中的子串按长度从小到大排序，则长度为连续的一段区间，记为 \([minlen,len]\)
-
\(endpos\) 等价类的个数为 \(O(n)\)
parent tree
根据上面的性质，如果 \(endpos(u)\subset endpos(v)\)，则 \(endpos(v)\) 代表节点设为 \(endpos(u)\) 的父节点
由 2 得兄弟节点之间的 \(endpos\) 不交
这样建出了一棵树，根节点为 \(root\)
SAM 的节点其实就是这棵树，从源点出发到达点 \(x\) 的任意一条路径形成的字符串的 \(endpos\) 集合都是节点 \(x\) 所代表的
我喜欢用这棵树，因为它有很好的性质
性质
这里设当前节点为 \(x\)，\(fa\) 为它的父亲
-
\(fa\) 对应的所有字符串为 \(x\) 对应的所有字符串的后缀
-
\(minlen(fa)=len(x)+1\)，也就是说，从 \(x\) 不断走向 parent tree 上的祖先节点，不重不漏的覆盖了串长 \([len(x),n]\)
-
原串两个前缀的 LCS（最长公共后缀），为它们代表的终止节点在 parent tree 上的 LCA 的 \(len\)
这里需要理解一下，由于一个串的后缀的 \(endpos\) 必定包含它，因此其实是找到 \(endpos\) 集合包含这两个节点的节点，就是 parent tree 上的 LCA 及它的祖先，而且要让串长最大，就选 LCA 的 \(len\)
实际应用时，可以对反串建 SAM，就能快速得出后缀的 LCP，可以代替后缀数组
本质上就是建了后缀树在用
-
每个节点的 \(endpos\) 为它子树内所有终止节点 \(endpos\) 的并集
很多时候可以用线段树合并之类的数据结构维护
-
设每个状态 \(endpos\) 的大小为 \(siz(x)\)，初始时只有终止节点的 \(siz(x)=1\)，每个节点的 \(siz\) 是子树内节点的 \(siz\) 之和
-
\(endpos\) 集合的大小，就代表这个等价类中，每个串在原串中出现了 \(siz\) 次
-
每个状态包含的本质不同子串个数：\(len(x)-len(fa)\)
根据 1 可得出，也可以理解为 \(x\) 扣掉了与 \(fa\) 重复的子串
SAM 的构建
SAM 的构建是在线的，依次插入原串末尾的字符，增量构造
SAM 上节点的 \(endpos\) 集合，代表着从初始节点走到它，形成的所有字符串在原串中出现位置的右端点集合
设当前正在插入字符串中第 \(n\) 个字符
步骤：
-
先在上一个终止节点 \(p\) 后新建节点 \(np\)，作为新的终止节点，显然 \(len(np)=len(p)+1\)
-
在 parent tree 上不断令 \(p=fa(p)\)，\(p\) 对应的字符串加上字符 \(c\) 后为新串后缀，如果 \(trie(p,c)\) 为空，则意味着从它们走到 \(np\) 节点，\(endpos(np)\) 目前都为 \(\{n\}\)，直接连边
-
如果 \(p\) 跳出了树，则说明字符 \(c\) 第一次出现，直接将 \(fa(np)\) 设为 \(root\)
-
否则令 \(q=trie(p,c)\)，此时 \(len(q)\ge len(p)+1\)
- 如果 \(len(q)=len(p)+1\)，说明 \(q\) 代表的所有字符串为新串后缀，那么令 \(fa(np)=q\)
- 否则 \(q\) 中不是所有节点都是新串后缀，此时要把是的拆出来，它们的 \(endpos\) 多了 \(n\)，新建节点 \(nq\)，转移（即边）和 \(q\) 相同，\(endpos(nq)=endpos(q)\cup \{n\}\)，\(fa(nq)=fa(q)\)，\(fa(q)=fa(np)=nq\)，还要把原来连向 \(q\) 的改为连向 \(nq\)
如果需要求出每个节点的 \(endpos\) 大小，则在新建 \(np\) 时令 \(siz(np)=1\)，然后每个节点的 \(siz\) 就是 parent tree 上子树中 \(siz\) 的和
struct SAM
{
void add(int c)
{
int p = las, np = las = ++idx;
siz[np] = 1, len[np] = len[p] + 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np; // 从长到短遍历原来串的所有后缀
if(!p) fa[np] = root; // case 1：之前没有 c字符
else
{
int q = ch[p][c]; // len[q] >= len[p] + 1
if(len[q] == len[p] + 1) fa[np] = q; // case 2：说明 q代表的所有子串 endpos集合中增加 n
else // case 3：q中 len > len[p]+1的子串 endpos没有 n，把增加 n的拆出来，成为 q的父亲
{
int nq = ++idx; // endpos(q) \in endpos(nq)
memcpy(ch[nq], ch[q], sizeof(ch[q])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
} // 增加 c后，这些 p的 endpos中也多 n，连到 nq上
}
}
void dfs(int x)
{
for(int y : edge[x]) dfs(y), siz[x] += siz[y];
if(siz[x] != 1) ans = max(ans, 1ll * len[x] * siz[x]);
}
void build()
{
for(int i = 2; i <= idx; ++i) edge[fa[i]].pb(i);
dfs(1);
}
}sam;
应用
判断串 \(T\) 是否为串 \(S\) 的子串
从初始节点沿着自动机的边匹配 \(T\)，如果跑出了自动机则不是
求本质不同子串个数
直接求 \(\sum_{x} len(x)-len(fa_x)\)，在 DAG 上 DP 也可以
求字典序第 \(k\) 大的子串
首先看不同位置出现算多次的情况
找到 \(siz\) 后，可以设 \(f(x)\) 表示走到 \(x\) 后还能表示的子串个数（包括就在 \(x\) 停止），在 DAG 上 DP
初始为 \(siz(root)=0,f(x)=siz(x)\)，转移为 \(f(x)\gets \sum_{trie(x,c)=y}f(y)\)
因为走到 \(x\) 时，前面已经确定了，只是在字符串中有 \(siz(x)\) 种可能的位置，而后面的不确定
然后从初始节点开始，按字典序，试着走每条边
-
如果 \(f(trie(x,c))>k\)，说明还有多的，\(k\to k-f(trie(x,c))\)
-
否则 \(f(trie(x,c))\le k\)，则字符串中插入 \(c\)，\(x=trie(x,c)\)
注意每到一个新节点时，\(k\) 减去这个节点的 \(siz\)，表示要往后走，不在当前点停留
如果 \(k\le 0\) 则退出
如果不同位置出现只算一次，那就让所有 \(siz(x)=1\) 即可
注意判断无解
struct SAM
{
void add(int c)
{
int p = las, np = las = ++idx;
siz[np] = 1, len[np] = len[p] + 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) fa[np] = root;
else
{
int q = ch[p][c];
if(len[q] == len[p] + 1) fa[np] = q;
else
{
int nq = ++idx;
memcpy(ch[nq], ch[q], sizeof(ch[q])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
}
}
void dfs(int x)
{
for(int y : edge[x]) dfs(y), siz[x] += siz[y];
}
void dfssam(int x)
{
book[x] = 1;
for(int i = 0; i < 26; ++i)
if(ch[x][i])
{
if(!book[ch[x][i]]) dfssam(ch[x][i]);
f[x] += f[ch[x][i]];
}
}
void build()
{
for(int i = 2; i <= idx; ++i) edge[fa[i]].pb(i);
dfs(root);
if(!t)
for(int i = 1; i <= idx; ++i) siz[i] = f[i] = 1;
else for(int i = 1; i <= idx; ++i) f[i] = siz[i];
dfssam(root), siz[root] = 0;
}
void findans(int u, ll k)
{
k -= siz[u];
if(k <= 0) return;
for(int i = 0; i < 26; ++i)
if(ch[u][i])
{
if(k > f[ch[u][i]]) k -= f[ch[u][i]];
else
{
putchar(i + 'a'), findans(ch[u][i], k);
return;
}
}
}
}sam;
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> (s + 1) >> t >> k, n = strlen(s + 1);
for(int i = 1; i <= n; ++i) sam.add(s[i] - 'a');
sam.build();
if(!t && k > f[root]) {printf("-1"); return 0;}
if(t && k > 1ll * n * (n - 1) / 2) {printf("-1"); return 0;}
sam.findans(root, k);
return 0;
}
多组询问 \(T\) 在给定串 \(S\) 中的出现次数
在 SAM 上直接通过转移边匹配 \(T\)，答案为最后走到的节点的 \(siz\)，单次查询复杂度为 \(O(|T|)\)
多个字符串的最长公共子串
对其中一个建 SAM，将其它的放在 SAM 上匹配
能沿着转移走就走，匹配的长度 \(+1\)，否则跳 \(fa\)，直到能走 \(trie(x,c)\) 匹配，匹配长度为 \(len(x)+1\)
如果一个状态能匹配到，则它在 parent tree 上的祖先节点也可以，因为一个子串如果被匹配到了，那么它的后缀也一定被匹配到
对于当前串，每个状态匹配长度的最大值为子树中的最大值
记录每个状态其它串在它上面匹配的最长长度的最小值，答案为所有状态的最大值
或者暴力把每个字符都插入 SAM，匹配所有的，看哪个状态被匹配 \(n\) 次，才能更新答案
例题
查询子串相关问题考虑建出 SAM
答案显然可二分，如果我们二分的答案为 \(x\)，就要求 \([l+x-1,r]\) 内出现两个结尾
在 SAM 上即对应 \(endpos\) 集合
现在问题变成了 SAM 上要找出一个对应 \(len\) 最大的节点，使它代表的 \(endpos\) 集合中有两个位置出现在指定区间内
考虑什么样的位置对会对答案造成贡献
在 parent tree 上，子节点的 \(len\) 比父节点要大，如果子节点子树内，已经有两个位置被区间包含了，那么在父节点处，这对不贡献
所以现在目标变成了对于树上每个点 \(x\) 找出这样的支配对，使得这两点必须来自 \(x\) 的不同子树，且序列上不完全包含其它的
维护 \(endpos\) 集合，使用 set 启发式合并，每次合并时，找到新插入点的前驱和后继，则它们构成支配对
不难由启发式合并的复杂度分析，得出支配对总共有 \(O(n\log n)\) 对
那么把这些支配对左端点位置在右端点所在主席树上更新贡献，查询时先二分答案，再在主席树上二分判定
时空复杂度均为 \(O(n\log^2n)\)
struct SAM
{
int ch[N][26], root = 1, idx = 1, las = 1, fa[N], len[N], id[N];
vector<int> edge[N]; set<int> ep[N];
void insert(int pos, int c)
{
int p = las, np = ++idx; las = np;
len[np] = len[p] + 1; ep[np].insert(pos);
for(; !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) {fa[np] = root; return;}
int q = ch[p][c];
if(len[q] == len[p] + 1) {fa[np] = q; return;}
int nq = ++idx;
memcpy(ch[nq], ch[q], sizeof(ch[nq])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
void merge(int &x, int &y, int l)
{
if(ep[x].size() < ep[y].size()) swap(x, y);
for(iter it = ep[y].begin(); it != ep[y].end(); ++it)
{
iter pre = ep[x].lower_bound(*it), nxt = ep[x].upper_bound(*it);
if(nxt != ep[x].end()) zpd[*nxt].pb({*it, l});
if(pre != ep[x].begin()) zpd[*it].pb({*prev(pre), l});
}
ep[x].insert(ep[y].begin(), ep[y].end());
}
void dfs(int x)
{
for(int y : edge[x])
{
dfs(y);
if(x != root) merge(id[x], id[y], len[x]);
}
}
void build()
{
for(int i = 1; i <= idx; ++i) edge[fa[i]].pb(i), id[i] = i;
dfs(root);
}
}sam;
struct chairmantree
{
int ls[M], rs[M], mx[M], idx;
int update(int pre, int id, int val, int l, int r)
{
int p = ++idx;
ls[p] = ls[pre], rs[p] = rs[pre], mx[p] = max(mx[pre], val);
if(l == r) return p;
int mid = (l + r) >> 1;
if(mid >= id) ls[p] = update(ls[p], id, val, l, mid);
else rs[p] = update(rs[p], id, val, mid + 1, r);
return p;
}
int query(int l, int r, int nl, int nr, int p)
{
if(!p) return 0;
if(l <= nl && nr <= r) return mx[p];
int mid = (nl + nr) >> 1, res = 0;
if(mid >= l) res = max(res, query(l, r, nl, mid, ls[p]));
if(mid < r) res = max(res, query(l, r, mid + 1, nr, rs[p]));
return res;
}
}tree;
int main()
{
cin >> n >> q >> (s + 1);
for(int i = 1; i <= n; ++i) sam.insert(i, s[i] - 'a');
sam.build();
for(int i = 1; i <= n; ++i)
{
root[i] = root[i - 1];
for(pii x : zpd[i])
root[i] = tree.update(root[i], x.fi, x.se, 1, n);
}
for(int i = 1; i <= q; ++i)
{
cin >> li >> ri;
int l = 0, r = ri - li + 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(tree.query(li + mid - 1, ri, 1, n, root[ri]) >= mid) l = mid;
else r = mid - 1;
}
cout << l << "\n";
}
return 0;
}
DP 好题
首先翻转序列，变为选有序串组使前一个为后一个的子串
性质 1：答案不超过 \(O(\sqrt n)\)
个数最多时，串长为 \(1,2,3,\dots\)，最多只有 \(O(\sqrt n)\) 个
性质 2：最优方案中串的长度肯定是 \(1,2,\dots,k\)
如果某两个串中间空了一个长度，那么把后面一个串删掉一个字母不影响答案，且可能匹配后面的更多字符串
性质 3：\(t_i\) 一定由 \(t_{i-1}\) 在首/尾增加一个字母得到
由性质 2 得长度增加 1
现在已经可以得到 \(O(n\sqrt n)\) 的做法，直接暴力哈希记录每种长度的字符串，优化卡常即可
但是此题可以线性（忽略 \(|\Sigma|\)）
建出翻转后串的 SAM，我们考虑 DP，设 \(f_i\) 表示 \(t_k\) 以 \(i\) 结尾方案中最大的 \(k\)
性质 4：\((i-1)-f_{i-1}+1\le i-f_i+1\)，即 \(i\) 处 \(t_k\) 的开头比 \(i-1\) 处的更靠后
反证法，如果不是，则能把 \(i-1\) 的开头往左移至 \(i-f_i+1\)，使 \(f_{i-1}\) 更大
既然右端点递增的同时左端点不降，就可以双指针
\(r\) 向右一位，设它在 SAM 上对应的状态为 \(p\)
它前一个字符串应该是 \([l+1,r]\) 或 \([l,r-1]\)，以 \([l,r-1]\) 为例，它在 SAM 上对应状态的 \(endpos\) 集合中，存在 \(<l\) 的位置 \(i\)，\(f_i\ge r-l\)，当前检查这两个串，看它们是否能满足条件，若不满足则 \(l\gets l+1\)
由于 \(l\) 单调移动，因此每次 \(l+1\) 时，我们把 \(f_l\) 对应字符串在 SAM 上更新，暴力从它对应的最优串的状态开始，一路跳 \(fa\)，它的每个后缀合法，且 \(f\) 应该取到了对应状态的 \(len\)，因为 \(len\le f_l\)
记录每个状态对应的这样的最大 \(f\) 为 \(g_x\)，尝试将 \(g_x\) 更新，如果遇到了更大的 \(g\) 或者是 \(g\) 已经与 \(len\) 相等就停止，因为上面的若 \(g\) 更大显然不用更新，若 \(g_x=len_x\) 则祖先处也满足 \(g_x=len_x\)，注意最先开始的状态不一定满足 \(g=len\)，要用 \(f_l\) 去更新
这样发现 SAM 上每个节点被访问到常数次，时间复杂度均摊 \(O(n)\)
struct SAM
{
int ch[N][26], len[N], fa[N], f[N], idx = 1, las = 1, root = 1;
void insert(int c)
{
int p = las, np = ++idx; las = np;
len[np] = len[p] + 1;
for(; !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) {fa[np] = root; return;}
int q = ch[p][c];
if(len[q] == len[p] + 1) {fa[np] = q; return;}
int nq = ++idx;
memcpy(ch[nq], ch[q], sizeof(ch[q])), len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
void upd(int p, int val)
{
f[p] = max(f[p], val);
for(p = fa[p]; p && f[p] < len[p]; p = fa[p]) f[p] = len[p]; // fa[p] should all be full
}
void work()
{
int l = 1, p = root, q = root;
for(int r = 1; r <= n; ++r) // p:[l,r] fa[p]:[l+1,r] q:[l,r-1]
{
q = p, p = ch[p][s[r] - 'a'];
while(l < r)
{
if(max({f[p], f[fa[p]], f[q]}) >= r - l) break;
upd(abl[l], ans[l]), ++l; // enable [l-ans[l]+1,l]
while(p && len[fa[p]] > r - l) p = fa[p]; // find new state
while(q && len[fa[q]] >= r - l) q = fa[q];
}
ans[r] = r - l + 1, abl[r] = p, sum = max(sum, ans[r]);
}
}
}sam;
int main()
{
cin >> n >> (s + 1);
reverse(s + 1, s + n + 1);
for(int i = 1; i <= n; ++i) sam.insert(s[i] - 'a');
sam.work();
cout << sum;
return 0;
}