本文没有构造证明,因为我不会
基础概念看看就好,自娱自乐。
后期重点更新相关题目的简单总结,方便复习
S 的后缀自动机是一种能够识别所有 S 的子串的自动机类型的数据结构(DFA)。
暴力后缀自动机
对于字符串 \(S\),建立插入了 \(|S|\) 个后缀的 Trie 树。这样显然可以查到所有的子串,但时空复杂度都为 \(O(n^2)\) ,显然不可取,考虑如何优化
最简状态后缀自动机
给出结论:状态数 \(O(2*n)\),转移数 \(O(3*n)\)
我们定义 \(Right(s)={r_1,r_2,...,r_m}\) ,表示 \(s\) 状态代表子串的出现位置右端点。
设两个状态 \(s\) 和 \(s′\),其 \(Right\) 集合分别为 \(R(s)\) 和 \(R(s′)\)。
假设 \(R(s) ∩ R(s′) = ∅\),并且 \(r ∈ R(s) ∩ R(s′)\)。
由于任何两个状态代表的串互不相同,不失一般性,可以认为 \(s\) 代表的
串都比 \(s′\) 代表的串长。
因此必然有 \(R(s) ⫋ R(s′)\)。
结论:两个不同状态的 Right 集合只存在两种关系:不相交,或者真包含。即形成一种树形结构。
Parent 树、link 树
由 \(Right\) 集合的包含关系形成的树。
\(f(s)\) 表示状态 \(s\) 对应的 \(Right(s)\) 在 \(SC\) 树上的父节点。
SC树性质
结点数为 \(O(2*n)\)
转移数为 \(O(3*n)\)。\(|2S-1|\) 树边 + \(S\) 条非树边,每个后缀对应一条非树边。
小结
const int maxn = 1e6 + 10; struct SAM { //basic const char* s; int last, cnt, len; int nxt[maxn * 2][26],fa[maxn * 2],l[maxn * 2]; //extension int cntA[maxn * 2], id[maxn * 2];/*辅助拓扑更新*/ int num[maxn * 2];/*每个节点代表的所有串的出现次数*/ SAM () { clear(); } void clear() { last = cnt = 1, l[1] = fa[1] = 0, memset(nxt[1], 0, sizeof nxt[1]); } void init(const char * str, int _len) { s = str, len = _len; for (int i = 1; i <= _len; i++) extend(str[i] - 'a'); } void extend(int c) { int p = last, np = ++cnt; memset(nxt[cnt], 0, sizeof nxt[cnt]); l[np] = l[p] + 1, last = np; while (p && !nxt[p][c]) nxt[p][c] = np, p = fa[p]; if (!p) fa[np] = 1; else { int q = nxt[p][c]; if (l[q] == l[p] + 1) fa[np] = q; else { int nq = ++cnt; l[nq] = l[p] + 1; memcpy(nxt[nq], nxt[q], sizeof(nxt[q])); fa[nq] = fa[q], fa[np] = fa[q] = nq; while (nxt[p][c] == q) nxt[p][c] = nq, p = fa[p]; } } } void build() { memset(cntA, 0, sizeof cntA); memset(num, 0, sizeof num); for (int i = 1; i <= cnt; i++) cntA[l[i]]++; for (int i = 1; i <= cnt; i++) cntA[i] += cntA[i - 1]; for (int i = cnt; i >= 1; i--) id[cntA[l[i]]--] = i; /*更新主串节点*/ int temp = 1; for (int i = 1; i <= len; i++) { num[temp = nxt[temp][s[i] - 'a']] = 1; } /*拓扑更新*/ for (int i = cnt; i >= 1; i--) { // basic int x = id[i]; num[fa[x]] += num[x]; // extension } // extension } void debug(){ for (int i = cnt; i >= 1; i--){ printf("num[%d]=%d l[%d]=%d fa[%d]=%d\n",i,num[i],i,l[i],i,fa[i]); } } }sam;
l[x] >= r - l + 1
的点,返回它的 \(|Right|\) 集合大小就是子串的出现次数。sz[ne] >= k
时,k --, now = ne, break;
sz[u] = num[u], sz[u] += sz[v]
,初始由 1 变成 num[u]
出现次数sz[ne] >= k
执行 k -= num[ne]
sz[np] = 1
,然后拓扑序更新。l[p]-l[fa[p]]
,答案就是树上所有路径之和。(n-sz[x])*sz[x]
次,乘上边权在倒序拓扑时直接统计即可。洛谷P4248 [AHOI2013]差异
pre[u] = pre[fa[u]] + l[fa[u]] - l[fa[fa[u]]
pre[now] + num[now] * (len - l[fa[now]])
即可。洛谷P3181 [HAOI2016]找相同字符
在含有多个串信息的 Trie 上建立SAM。有离线和在线两种构造方法,直接给出模板
const int maxn = 1e6 + 10; struct Trie { int idx, fa[maxn], son[maxn][26], c[maxn]; Trie() {idx = 1;} void insert(const char* s) { int p = 1; for (int i = 1; s[i]; i++) { int u = s[i] - 'a'; if (!son[p][u]) son[p][u] = ++idx, fa[idx] = p, c[idx] = u; p = son[p][u]; } } }Tr; struct SAM { //basic const char* s; int cnt, len; int nxt[maxn * 2][26],fa[maxn * 2],l[maxn * 2]; queue<int> q; //extension int cntA[maxn * 2], id[maxn * 2];/*辅助拓扑更新*/ int num[maxn * 2];/*每个节点代表的所有串的出现次数*/ int pos[maxn * 2]; // Trie 上节点在 SAM 上对应的节点编号 SAM () { clear(); } void clear() { cnt = 1, l[1] = fa[1] = 0, memset(nxt[1], 0, sizeof nxt[1]); } void init() { for (int i = 0; i < 26; i++) if (Tr.son[1][i]) q.push(Tr.son[1][i]); pos[1] = 1; while (!q.empty()) { int t = q.front(); q.pop(); pos[t] = extend(Tr.c[t], pos[Tr.fa[t]]); for (int i = 0; i < 26; i++) if (Tr.son[t][i]) q.push(Tr.son[t][i]); } } int extend(int c, int last) { int p = last, np = ++cnt; memset(nxt[cnt], 0, sizeof nxt[cnt]); l[np] = l[p] + 1, last = np; while (p && !nxt[p][c]) nxt[p][c] = np, p = fa[p]; if (!p) fa[np] = 1; else { int q = nxt[p][c]; if (l[q] == l[p] + 1) fa[np] = q; else { int nq = ++cnt; l[nq] = l[p] + 1; memcpy(nxt[nq], nxt[q], sizeof(nxt[q])); fa[nq] = fa[q], fa[np] = fa[q] = nq; while (nxt[p][c] == q) nxt[p][c] = nq, p = fa[p]; } } return np; } void build() { memset(cntA, 0, sizeof cntA); memset(num, 0, sizeof num); for (int i = 1; i <= cnt; i++) cntA[l[i]]++; for (int i = 1; i <= cnt; i++) cntA[i] += cntA[i - 1]; for (int i = cnt; i >= 1; i--) id[cntA[l[i]]--] = i; /*更新主串节点*/ int temp = 1; for (int i = 1; i <= len; i++) { num[temp = nxt[temp][s[i] - 'a']] = 1; } /*拓扑更新*/ for (int i = cnt; i >= 1; i--) { // basic int x = id[i]; num[fa[x]] += num[x]; // extension } // extension } void debug(){ for (int i = cnt; i >= 1; i--){ printf("num[%d]=%d l[%d]=%d fa[%d]=%d\n",i,num[i],i,l[i],i,fa[i]); } } }exsam;
const int maxn = 2e6 + 10; struct EXSAM { //basic const char* s; int cnt, len; int nxt[maxn * 2][26],fa[maxn * 2],l[maxn * 2]; //extension queue<int> q; int cntA[maxn * 2], id[maxn * 2];/*辅助拓扑更新*/ int num[maxn * 2];/*每个节点代表的所有串的出现次数*/ EXSAM () { clear(); } void clear() { cnt = 1, l[1] = fa[1] = 0, memset(nxt[1], 0, sizeof nxt[1]), memset(num, 0, sizeof num); } int extend(int c, int last, int idx = 0) { if (nxt[last][c]) { int p = last, x = nxt[p][c]; if (l[p] + 1 == l[x]) { num[x] = 1; return x;} int y = ++cnt; l[y] = l[p] + 1; memcpy(nxt[y], nxt[x], sizeof nxt[x]); while (p && nxt[p][c] == x) nxt[p][c] = y, p = fa[p]; fa[y] = fa[x], fa[x] = y; num[y] = 1; return y; } int p = last, np = ++cnt; memset(nxt[cnt], 0, sizeof nxt[cnt]); l[np] = l[p] + 1, last = np; while (p && !nxt[p][c]) nxt[p][c] = np, p = fa[p]; if (!p) fa[np] = 1; else { int q = nxt[p][c]; if (l[q] == l[p] + 1) fa[np] = q; else { int nq = ++cnt; l[nq] = l[p] + 1; memcpy(nxt[nq], nxt[q], sizeof(nxt[q])); fa[nq] = fa[q], fa[np] = fa[q] = nq; while (nxt[p][c] == q) nxt[p][c] = nq, p = fa[p]; } } num[np] = 1; return np; } void build() { memset(cntA, 0, sizeof cntA); for (int i = 2; i <= cnt; i++) ++ cntA[fa[i]]; for (int i = 1; i <= cnt; i++) if (!cntA[i]) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < 2; i++) num[fa[u]] += num[u]; if (!(--cntA[fa[u]])) q.push(fa[u]); } } }exsam;
题意
给出一颗叶子结点不超过 \(20\) 个的无根树,每个节点上都有一个不超过 \(10\) 的数字,求树上本质不同的路径个数(两条路径相同定义为:其路径上所有节点上的数字依次相连组成的字符串相同)
思路
辰星凌【学习笔记】字符串—广义后缀自动机
牛客竞赛字符串-后缀自动机