后缀自动机好难理解啊，看了一上午，感觉理解了一半吧……边做题边加深理解吧
这两篇博客讲的不错，下面写很多是这两篇博客的内容
史上最通俗的后缀自动机详解 - KesdiaelKen 的博客 - 洛谷博客
浅谈后缀自动鸡/SAM - Arextre 的博客 - 洛谷博客
后来又在b站上看到不错的讲解 按照视频说的当作黑盒使用吧，深究原理好痛苦
史上最易懂的后缀自动机讲解！独创理解思路还有例题讲解~_哔哩哔哩_bilibili
本质上是将一个字符串的所有子串的信息聚集在一个有向无环图中
一开始有一个源点，一条边代表在末尾添加一个字符
每一个节点代表一个endpos等价类，一个类中有很多个子串，它们长度连续，且短的为长的后缀
一条路径所形成的字符串一定在终点节点的等价类中
一个点的父亲是另一类边（有两类边），代表当前等价类的，父亲类所代表的子串是儿子类所代表字串的后缀
建出一个trie树，到达一个点又很多路径，这个点包含了所有到达这个点的所有路径形成的字符串
还建立一个fail树，fail指针指向当前字符串的后缀中最长的后缀所在的点
P3804 【模板】后缀自动机 (SAM)#include#define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; typedef long long ll; const int N = 2e6 + 10; //字符串总长两倍 int t[N][26], len[N], fa[N], c[N], k[N]; //t为自动机上的边，即fail，fa为parent tree上的边 int siz[N], cnt = 1, last = 1, n; //len表示节点i的类中最长串的长度 vector endpos[N]; char s[N]; ll ans; void add(int c, int pos) //题目不同更新u，r两处 不只有小写字母也要改 { int p = last; int u = last = ++cnt; //u是新建的节点 len[u] = len[p] + 1; for(; p && !t[p][c]; p = fa[p]) t[p][c] = u; if(!p) fa[u] = 1; else { int q = t[p][c]; if(len[q] == len[p] + 1) fa[u] = q; else { int r = ++cnt; //r是多建的虚空点 _for(i, 0, 25) t[r][i] = t[q][i]; //有些题不只是小写字母 注意 fa[r] = fa[q]; len[r] = len[p] + 1; fa[q] = fa[u] = r; for(; p && t[p][c] == q; p = fa[p]) t[p][c] = r; //更新r } } //更新u siz[u] = 1; //注意siz的初始化只有siz[u] = 1 不要写siz[q] = 1 endpos[u].push_back(pos); //siz表示有多少个终止位置，也是子串出现次数 } int main() { scanf("%s", s + 1); n = strlen(s + 1); _for(i, 1, n) add(s[i] - 'a', i); _for(i, 1, cnt) c[len[i]]++; //根据len桶排序 也可以dfs求siz数组 _for(i, 1, cnt) c[i] += c[i - 1]; _for(i, 1, cnt) k[c[len[i]]--] = i; for(int i = cnt; i >= 1; i--) { int id = k[i]; siz[fa[id]] += siz[id]; for(int x: endpos[id]) endpos[fa[id]].push_back(x); } _for(i, 1, n) if(siz[i] > 1) ans = max(ans, 1LL * siz[i] * len[i]); printf("%lldn", ans); return 0; }
应用
1.求一个串是否为另一个串的字串
SAM就是集合了一个串所有子串的信息
建立SAM，然后在SAM上跑就行
没有跑到空就是子串
用SA的话，要把两个串拼在一起，查看height数组。是否有height值等于串长度且在两个串中。
2.两个串的最长公共子串
SAM：一个建SAM，另一个在SAM上跑，看能跑多长，跑不了就往父亲跑
SA：拼在一起，遍历height数组，找在两个串中且最大的值
3.不同字串个数
SAM：遍历每个点，它代表的字符串个数就是len[i] - len[fa[i]] 遍历每个点即可。或者统计从开始节点走有多少个不同路径，有向无环图上dp即可，f[i]表示从i节点出发的路径数
SA：遍历每一个后缀，贡献为当前后缀长度减去重复的height
周二 poj 3415（后缀自动机）好题，妙啊
我开始觉得可以用后缀数组写，按照height分组，但是发现同一组内的两个后缀统计答案的时候要O（n^2） 没有想到什么优化的方法。不过看到有人是用后缀数组做的，用单调栈优化。
这题用后缀自动机会简单粗暴一点
首先对a串建立后缀自动机，然后b串在这上面跑
跑到一个点时，其实在a串上就对应跑到小于等于当前长度的所有后缀
这时候要分两部分，一个是fail的部分，这部分是可以全部包含的，一个是当前点的部分，这部分只有小于等于当前长度的后缀是可以跑到的，并不能跑到这个点所代表的字符串的所有集合
对于fail的部分，我们用一个数组记录一下，最后在parent tree上求子树和，类似求子串出现的次数，只不过这里是求b串在自动机上出现的次数，而不是a串自己。
第二部分是当前部分的统计，这时也用一个数组，直接统计当前的贡献就行了
统计的时候有两个限制，一个是K的限制，一个是集合大小的限制
最后一起答案，每个节点的贡献为A串出现次数*B串出现次数*符合条件的字符串个数
#includeP3975 [TJOI2015]弦论（后缀自动机）#include #include #define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; typedef long long ll; const int N = 1e5 + 10; int t[N << 1][60], len[N << 1], fa[N << 1], c[N << 1], k[N << 1], K; int siz[N << 1], num[N << 1], sum[N << 1], cnt, last, n; char s[N], b[N]; ll ans; void add(int c) { int p = last; int u = last = ++cnt; len[u] = len[p] + 1; for(; p && !t[p][c]; p = fa[p]) t[p][c] = u; if(!p) fa[u] = 1; else { int q = t[p][c]; if(len[q] == len[p] + 1) fa[u] = q; else { int r = ++cnt; rep(i, 0, 60) t[r][i] = t[q][i]; fa[r] = fa[q]; len[r] = len[p] + 1; fa[q] = fa[u] = r; for(; p && t[p][c] == q; p = fa[p]) t[p][c] = r; } } siz[u] = 1; } int main() { while(scanf("%d", &K) && K) { cnt = last = 1; memset(t, 0, sizeof t); scanf("%s%s", s + 1, b + 1); n = strlen(s + 1); _for(i, 1, n) add(s[i] - 'A'); int temp = strlen(b + 1), u = 1, cur = 0; _for(i, 1, temp) { int c = b[i] - 'A'; while(u && !t[u][c]) u = fa[u], cur = len[u]; if(!u) u = 1, cur = 0; else u = t[u][c], cur++; num[fa[u]]++; sum[u] += max(min(cur - K + 1, cur - len[fa[u]]), 0); } ans = 0; _for(i, 1, cnt) c[len[i]]++; _for(i, 1, cnt) c[i] += c[i - 1]; _for(i, 1, cnt) k[c[len[i]]--] = i; for(int i = cnt; i >= 1; i--) { int x = k[i]; siz[fa[x]] += siz[x]; num[fa[x]] += num[x]; ans += 1LL * siz[x] * num[x] * max(min(len[x] - K + 1, len[x] - len[fa[x]]), 0); ans += 1LL * siz[x] * sum[x]; } printf("%lldn", ans); _for(i, 1, cnt) sum[i] = siz[i] = num[i] = k[i] = c[i] = 0; } return 0; }
求第k大子串大小，加深了我对SAM的理解
求一个sum数组，表示在自动机上跑经过点u的子串的数量，也就是经过u能跑到多少个点，因为跑到一个点就是一个子串。
如果是本质不同的情况，那就是一个点初始化为1，然后求能达到的所有点的点权和。
如果是本质相同的情况，那个一个点就初始化为siz，也就是出现的次数。
然后注意1节点要初始化为0
区分不同的子串（自动机上），一个子串出现次数（parent tree上）
#includeC. Cyclical Quest（后缀自动机）#define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; const int N = 1e6 + 10; int t[N][26], len[N], fa[N], c[N], k[N]; int siz[N], sum[N], cnt = 1, last = 1, n, K, op; char s[N]; void add(int c) { int p = last; int u = last = ++cnt; len[u] = len[p] + 1; for(; p && !t[p][c]; p = fa[p]) t[p][c] = u; if(!p) fa[u] = 1; else { int q = t[p][c]; if(len[q] == len[p] + 1) fa[u] = q; else { int r = ++cnt; _for(i, 0, 25) t[r][i] = t[q][i]; fa[r] = fa[q]; len[r] = len[p] + 1; fa[q] = fa[u] = r; for(; p && t[p][c] == q; p = fa[p]) t[p][c] = r; } } siz[u] = 1; } void dfs(int u, int cur) { if(cur <= 0) return; rep(i, 0, 26) if(t[u][i]) { if(cur > sum[t[u][i]]) cur -= sum[t[u][i]]; else { putchar(i + 'a'); dfs(t[u][i], cur - siz[t[u][i]]); break; } } } int main() { scanf("%s%d%d", s + 1, &op, &K); n = strlen(s + 1); _for(i, 1, n) add(s[i] - 'a'); _for(i, 1, cnt) c[len[i]]++; _for(i, 1, cnt) c[i] += c[i - 1]; _for(i, 1, cnt) k[c[len[i]]--] = i; for(int i = cnt; i >= 1; i--) siz[fa[k[i]]] += siz[k[i]]; _for(i, 1, cnt) { if(!op) sum[i] = siz[i] = 1; else sum[i] = siz[i]; } sum[1] = siz[1] = 0; //1节点为0 for(int i = cnt; i >= 1; i--) rep(j, 0, 26) if(t[k[i]][j]) sum[k[i]] += sum[t[k[i]][j]]; if(sum[1] < K) puts("-1"); else dfs(1, K); return 0; }
给一个串S，每次询问一个串T，问S串中有多少个子串与T循环同构
如果不考虑循环同构，即T串在S串中出现了多少次，那么在SAM上预处理出每一个点的endpos集合个数，也就是出现了多少次，然后T串在上面跑，跑到某个点，某个点的这个值就是答案
考虑循环同构，循环同构常见的 *** 作是把字符串加倍，这道题也一样
于是我们把字符串加倍，在S串上的SAM上跑。在这个加倍的串中，一个长度为T串长度的子串就是一个循环同构的串。我们边跑边统计匹配长度，当匹配长度大于等于T串长度时，我们就要统计答案
怎么统计答案呢，当前节点的endpos集合个数不一定当前的贡献，需要跳fail，也就是说让当前匹配的后缀更短，在大于等于T串的条件下尽可能短，这时endpos集合个数才是答案
同时有一个细节，可能T串的不同的循环同构出来的串是一样的，按照题意只能算一次，所以要用一个vis数组来记录一下
#includeF. Forbidden Indices（后缀自动机）#define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; typedef long long ll; const int N = 2e6 + 10; int t[N][26], vis[N], len[N], fa[N], c[N], k[N]; int siz[N], sum[N], cnt = 1, last = 1, n; char s[N], a[N]; void add(int c) { int p = last; int u = last = ++cnt; len[u] = len[p] + 1; for(; p && !t[p][c]; p = fa[p]) t[p][c] = u; if(!p) fa[u] = 1; else { int q = t[p][c]; if(len[q] == len[p] + 1) fa[u] = q; else { int r = ++cnt; _for(i, 0, 25) t[r][i] = t[q][i]; fa[r] = fa[q]; len[r] = len[p] + 1; fa[q] = fa[u] = r; for(; p && t[p][c] == q; p = fa[p]) t[p][c] = r; } } siz[u] = 1; } int main() { scanf("%s", s + 1); n = strlen(s + 1); _for(i, 1, n) add(s[i] - 'a'); _for(i, 1, cnt) c[len[i]]++; _for(i, 1, cnt) c[i] += c[i - 1]; _for(i, 1, cnt) k[c[len[i]]--] = i; for(int i = cnt; i >= 1; i--) siz[fa[k[i]]] += siz[k[i]]; int T; scanf("%d", &T); _for(id, 1, T) { scanf("%s", a + 1); ll ans = 0; int lena = strlen(a + 1), u = 1, l = 0; _for(i, 1, lena * 2) { int c = i > lena ? a[i - lena] - 'a' : a[i] - 'a'; while(u && !t[u][c]) u = fa[u], l = len[u]; if(!u) u = 1, l = 0; else u = t[u][c], l++; if(l >= lena) { int v = u; while(!(len[v] >= lena && len[fa[v]] < lena)) v = fa[v]; if(vis[v] != id) { vis[v] = id; ans += siz[v]; } } } printf("%lldn", ans); } return 0; }
模板题，稍微改一改
禁止的时候，初始化为0就行
#include周三#define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; typedef long long ll; const int N = 4e5 + 10; int t[N][26], vis[N], len[N], fa[N], c[N], k[N]; int siz[N], cnt = 1, last = 1, n; char s[N]; void add(int c, int op) { int p = last; int u = last = ++cnt; len[u] = len[p] + 1; for(; p && !t[p][c]; p = fa[p]) t[p][c] = u; if(!p) fa[u] = 1; else { int q = t[p][c]; if(len[q] == len[p] + 1) fa[u] = q; else { int r = ++cnt; _for(i, 0, 25) t[r][i] = t[q][i]; fa[r] = fa[q]; len[r] = len[p] + 1; fa[q] = fa[u] = r; for(; p && t[p][c] == q; p = fa[p]) t[p][c] = r; } } siz[u] = !op; } int main() { scanf("%d%s", &n, s + 1); _for(i, 1, n) { int x; scanf("%1d", &x); add(s[i] - 'a', x); } _for(i, 1, cnt) c[len[i]]++; _for(i, 1, cnt) c[i] += c[i - 1]; _for(i, 1, cnt) k[c[len[i]]--] = i; for(int i = cnt; i >= 1; i--) siz[fa[k[i]]] += siz[k[i]]; ll ans = 0; _for(i, 1, cnt) ans = max(ans, 1LL * len[i] * siz[i]); printf("%lldn", ans); return 0; }
做一道字符串的题，推出了做法是需要求以一个数为最小值的区间，我只记得这个可以用单调栈来做，但具体实现忘记了，复习一下
P5788 【模板】单调栈#include#define rep(i, a, b) for(int i = (a); i < (b); i++) #define _for(i, a, b) for(int i = (a); i <= (b); i++) using namespace std; const int N = 3e6 + 10; int a[N], ans[N], s[N], top, n; int main() { scanf("%d", &n); _for(i, 1, n) scanf("%d", &a[i]); for(int i = n; i >= 1; i--) { while(top && a[s[top]] <= a[i]) top--; //注意这里是while 不是 if 维持单调性 ans[i] = top ? s[top] : 0; //通过当前栈顶记录答案 s[++top] = i; //将当前元素压入栈 } _for(i, 1, n) printf("%d ", ans[i]); return 0; }
[数据结构]——单调栈_lucky52529的博客-CSDN博客_单调递增栈
这篇博客不错
单调栈伪代码
分三步 保持单调性 统计答案 压入
//添加结束标志，使得最后可以全部出栈 从而不会漏答案
for() //以某种顺序遍历数组
{
while(top && 不符合单调性)
{
top--;
统计答案
}
s.push(i); //入栈 注意压入的是下标，比较的是下标对应的值
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）