【题解】后缀自动机(SAM)选做(22.8.11)
2022/8/11 23:30:08
本文主要是介绍【题解】后缀自动机(SAM)选做(22.8.11),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
做完这些我才感觉我的后缀自动机入门了之前写的东西就是一坨屎
对于后缀自动机的学习,我总结了以下三句话:
千万不要死磕模板!!!
千万不要死磕模板!!!
千万不要死磕模板!!!
谁死磕模板谁&#*%#(@#
这次就主要是我对于后缀自动机的理解,只是纯纯的自动机,不包含如何构造,因为那东西实在不行就背背板子,下面开始正文。
重复旋律 5
题目描述:
求本质不同的子串个数。
题目分析:
我们知道后缀自动机的几个性质:
- 后缀自动机的每个状态代表 \(\text{endpos}\) 相同的子串的集合,后缀自动机可以接受一个字符串的所有子串
- 后缀自动机的每个状态包含的字符串不交,这些字符串且满足长度递减且连续,即其长度为 \(k,k-1,k-2,\cdots\),且均为最长的子串的后缀。
- 后缀自动机的 \(fail\) 指针指向当前状态内的最长子串的最长的不在当前状态的后缀,即 \(\text{endpos}\) 与当前状态不同。设这个后缀的长度为 \(len\),也就是说长度为 \(len+1\) 的后缀在这个状态里面。
由以上的性质我们可以发现:我们如果能够知道每一个状态其代表的字符串的个数,那么求和之后就是全部的本质不同的子串个数。
我们也可以得到:设状态 \(x\) 的最长子串的长度为 \(len[x]\),那么 \(x\) 内子串的长度为:\([len[fail[x]]+1,len[x]]\),也就是状态 \(x\) 内的子串数量为:\(len[x] - len[fail[x]]\)
代码详解:
点击查看代码
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXLEN = 1e6+5; const int MAXM = 2 * MAXLEN; //状态数是 2 * len - 1 const int MAXN = 2 * MAXLEN; const int ALP = 26; struct state{ //SAM 的结构体 int len,link; int nxt[27]; }st[MAXLEN * 2]; struct edge{ int nxt,to; edge(){} edge(int _nxt,int _to){ nxt = _nxt,to = _to; } }e[MAXM]; int sz,last,ans,tot[MAXN],head[MAXN],cnt; char s[MAXN]; void sam_init(){ //SAM 的初始化 st[0].len = 0;st[0].link = 0;sz=1;last=1; } void sam_extend(int c){ //SAM 的构造,以 1 号节点为源点 int p = last; int cur = last = ++sz; tot[cur] = 1; st[cur].len = st[p].len + 1; while(p && !st[p].nxt[c]){ st[p].nxt[c] = cur; p = st[p].link; } if(!p) st[cur].link = 1; else{ int q = st[p].nxt[c]; if(st[p].len + 1==st[q].len) st[cur].link = q; else{ int clone = ++sz; st[clone] = st[q];st[clone].len = st[p].len+1; while(p && st[p].nxt[c] == q){ st[p].nxt[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; } } } signed main(){ sam_init(); int n; scanf("%lld",&n); scanf("%s",s+1); for(int i=1; i<=n; i++) sam_extend(s[i] - 'a'); //构造自动机 int ans = 0; for(int i=1; i<=sz; i++) ans = ans + st[i].len - (st[st[i].link].len + 1) + 1; //推出的式子 printf("%lld\n",ans); return 0; }
重复旋律 6
题目描述:
求出长度为 \(1,2,3,\cdots,n\) 的子串中,出现次数最多的串的出现次数。
题目分析:
我们知道后缀自动机有以下的性质:
- 对于不同状态内的子串不交,即不存在两个状态可以接受同一个字符串
- 对于不同状态的 \(\text{endpos}\) 集合,只存在包含或没有交集的关系
我们会发现:如果我们可以知道 \(\text{endpos}\) 集合的大小,那么我们就可以知道当前状态下的子串的出现次数,因为对于不同的状态代表的子串一定不交,其的 \(\text{endpos}\) 只有包含与交集为空。
那么问题就是我们如何求解 \(\text{endpos}\) 集合的大小。
我们会发现在 \(fail\) 树中,\(i\) 出现的所有位置 \(fail[i]\) 都会出现,因为 \(fail[i]\) 代表的子串中有 \(i\) 代表的子串中的后缀,所以 \(i\) 的 \(\text{endpos}\) 集合的大小,就是所有它在 \(fail\) 树上的儿子的 \(\text{endpos}\) 集合的大小之和。
但是这样会有一个特例:当状态 \(i\) 不是分裂出去的点,也就是 \(i\) 是正常的原串的前缀的话,其 \(\text{endpos}\) 集合会加一。
因为在这个位置出现的只能是这个前缀或者是这个前缀的后缀,而显然它的儿子中不可能是它的后缀,相反它可能是他的儿子的后缀。
总结一下步骤:
- 求解 \(\text{endpos}\) 集合大小
- 使用 \(\text{endpos}\) 集合大小获取每个状态的对应的字符串的出现次数
代码详解:
点击查看代码
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXLEN = 1e6+5; const int MAXM = 2 * MAXLEN; //状态数是 2 * len - 1 const int MAXN = 2 * MAXLEN; const int ALP = 26; struct state{ //SAM 的结构体 int len,link; int nxt[27]; }st[MAXLEN * 2]; struct edge{ int nxt,to; edge(){} edge(int _nxt,int _to){ nxt = _nxt,to = _to; } }e[MAXM]; int sz,last,ans,endpos[MAXN],tot[MAXN],head[MAXN],cnt,res[MAXN]; char s[MAXN]; bool flag[MAXN]; void sam_init(){ //SAM 的初始化 st[0].len = 0;st[0].link = 0;sz=1;last=1; } void sam_extend(int c){ //SAM 的构造,以 1 号节点为源点 int p = last; int cur = last = ++sz;flag[sz] = true; tot[cur] = 1; st[cur].len = st[p].len + 1; while(p && !st[p].nxt[c]){ st[p].nxt[c] = cur; p = st[p].link; } if(!p) st[cur].link = 1; else{ int q = st[p].nxt[c]; if(st[p].len + 1==st[q].len) st[cur].link = q; else{ int clone = ++sz; st[clone] = st[q];st[clone].len = st[p].len+1; while(p && st[p].nxt[c] == q){ st[p].nxt[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; } } } void add_edge(int from,int to){ e[++cnt] = edge(head[from],to); head[from] = cnt; } void dfs(int now){ if(flag[now]) endpos[now] = 1; //判断是正常的后缀 for(int i = head[now]; i; i = e[i].nxt){ int to = e[i].to; dfs(to); endpos[now] += endpos[to]; } } signed main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); sam_init(); scanf("%s",s+1);int n = strlen(s+1); for(int i=1; i<=n; i++) sam_extend(s[i] - 'a'); for(int i=2; i<=sz; i++) add_edge(st[i].link,i); //建 fail 树 dfs(1); for(int i=1; i<=sz; i++) res[st[i].len] = max(res[st[i].len],endpos[i]); //这里很妙,因为对于 len 的每一个,[1,len] 这 len 的后缀肯定都出现了 for(int i=n-1; i>=1; i--) res[i] = max(res[i],res[i+1]); for(int i=1; i<=n; i++) printf("%lld\n",res[i]); return 0; }
重复旋律 7
题目描述:
给定若干个由数字构成的串,求所有串的子串所对应的数字的和。
例如 123
的结果就是:\(1 + 2 + 3 + 12 + 23 + 123 = 164\)
题目分析:
我们知道后缀自动机有以下性质:
- 由字符的转移所构成的图是一个有向无环图
那么我们就可以考虑在这个有向无环图上 \(DP\) 求解。我们先考虑如果只有一个串如何解决:
显然可以得到 \(dp[i]\) 表示以 \(i\) 为终点的子串的数字和。因为后缀自动机中可以接受所有的子串,所以将所有的 \(dp\) 值求和就是答案。
转移显然就是枚举字符的转移是哪个,假设为 \(x\)
其中 \(cnt[i]\) 代表到达状态 \(i\) 的路径条数,也就是以 \(i\) 为终点的子串数量(相信 \(cnt\) 数组都会求)
那么对于多个子串我们显然可以将这几个子串连起来,中间使用字符集之外的符号连接,这样我们的 \(cnt\) 和 \(dp\) 的定义就可以顺势改为不包含这个特殊符号的前提下。
代码详解:
点击查看代码
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXLEN = 1e6+5; const int MAXM = 2 * MAXLEN; //状态数是 2 * len - 1 const int MAXN = 2 * MAXLEN; const int ALP = 12; const int MOD = 1e9+7; struct state{ //SAM 的结构体 int len,link; int nxt[27]; }st[MAXLEN * 2]; struct edge{ int nxt,to; edge(){} edge(int _nxt,int _to){ nxt = _nxt,to = _to; } }e[MAXM]; int sz,last,tot[MAXN],head[MAXN],cnt[MAXN],val[MAXN],num[MAXN]; char s[MAXN]; void sam_init(){ //SAM 的初始化 st[0].len = 0;st[0].link = 0;sz=1;last=1; } void sam_extend(int c){ //SAM 的构造,以 1 号节点为源点 int p = last; int cur = last = ++sz; tot[cur] = 1; st[cur].len = st[p].len + 1; while(p && !st[p].nxt[c]){ st[p].nxt[c] = cur; p = st[p].link; } if(!p) st[cur].link = 1; else{ int q = st[p].nxt[c]; if(st[p].len + 1==st[q].len) st[cur].link = q; else{ int clone = ++sz; st[clone] = st[q];st[clone].len = st[p].len+1; while(p && st[p].nxt[c] == q){ st[p].nxt[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; } } } void topo(){ for(int i=1; i<=sz; i++){ for(int j=0; j<=10; j++){ if(st[i].nxt[j]) cnt[st[i].nxt[j]]++; //记录入度 } } queue<int> q;q.push(1); num[1] = 1; while(!q.empty()){ int now = q.front();q.pop(); for(int i=0; i<=10; i++){ int to = st[now].nxt[i]; if(to){ if(i != 10) val[to] = (val[to] + (val[now] * 10)%MOD + (i * num[now])%MOD)%MOD; //10 即字符集之外的特殊字符,不考虑这个字符 if(i != 10) num[to] = (num[to] + num[now])%MOD; cnt[to]--; if(cnt[to] == 0) q.push(to); } } } int ans = 0; for(int i=1; i<=sz; i++){ //对所有的状态累计 ans = (ans + val[i])%MOD; } printf("%lld\n",ans); } signed main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); sam_init(); int n;scanf("%lld",&n); for(int i=1; i<=n; i++){ scanf("%s",s+1);int m = strlen(s+1); for(int i=1; i<=m; i++) sam_extend(s[i] - '0'); if(i != n) sam_extend(10); } topo(); return 0; }
重复旋律 8
题目描述:
给定 \(n\) 个字符串 \(t\) 和一个字符串 \(s\),求 \(t\) 的所有循环同构在 \(s\) 中的出现次数,出现多次便重复统计。
题目分析:
对于循环同构我们显然可以将字符串倍长,然后判断长度为原长的字符串的出现次数。
我们可以考虑对于每一个字符串 \(t\) 该如何求解:
我们考虑对每一个 \(t[i]\) 作为结束位置维护两个值:\(u\) 表示以 \(t[i]\) 为结尾的最长公共子串对应的 SAM 里的状态,\(len\) 表示以 \(t[i]\) 为结尾的最长公共子串的长度。显然如果最长公共子串的长度大于等于原长,那么就意味着以 \(t[i]\) 为结尾的这个循环同构会出现 \(|\text{endpos}(u)|\) 次。
那么就考虑知道了 \(i\) 如何求解 \(i+1\):
对于这个的求解我们显然可以类似 KMP 去求解,如果失配,也就是当前的点没有 \(t[i+1]\) 的转移,那么就跳 \(fail\),直到跳到一个点有 \(t[i+1]\) 的转移,因为这样能保证最后的部分一定可以匹配,而如果跳到最后都没有 \(t[i+1]\) 的转移,那么就意味着这个字符串没出现过。
需要注意以下的几点细节:
- 我们如果多次到达某一个状态,那么只计算一次贡献。例如
aaaa
显然其循环同构只有aaaa
而非四个aaaa
。 - 我们可能在匹配的时候出现 \(len\) 大于原长的情况,那么此时我们现在的这个循环同构就是我们找到的状态的后缀,那么我们可能可以通过跳 \(fail\),使得 \(len\) 在大于等于原长的情况下尽可能小,这样就可能导致 \(|\text{endpos}|\) 变大。
可以发现我们求解一个字符串的时间复杂度是 \(O(|t|)\) 的,因为我们最多跳 \(|t|\) 次字符转移,也就是不可能跳超过 \(|t|\) 次 \(fail\)。
那么我们就对于所有的字符串每个都跑一遍就好了。
代码详解:
点击查看代码
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXLEN = 1e6+5; const int MAXM = 2 * MAXLEN; //状态数是 2 * len - 1 const int MAXN = 2 * MAXLEN; const int ALP = 26; struct state{ //SAM 的结构体 int len,link; int nxt[27]; }st[MAXLEN * 2]; struct edge{ int nxt,to; edge(){} edge(int _nxt,int _to){ nxt = _nxt,to = _to; } }e[MAXM]; int sz,last,ans,endpos[MAXN],tot[MAXN],head[MAXN],cnt,res[MAXN]; char s[MAXN],t[MAXN]; bool flag[MAXN],vis[MAXN]; void sam_init(){ //SAM 的初始化 st[0].len = 0;st[0].link = 0;sz=1;last=1; } void sam_extend(int c){ //SAM 的构造,以 1 号节点为源点 int p = last; int cur = last = ++sz;flag[sz] = true; tot[cur] = 1; st[cur].len = st[p].len + 1; while(p && !st[p].nxt[c]){ st[p].nxt[c] = cur; p = st[p].link; } if(!p) st[cur].link = 1; else{ int q = st[p].nxt[c]; if(st[p].len + 1==st[q].len) st[cur].link = q; else{ int clone = ++sz; st[clone] = st[q];st[clone].len = st[p].len+1; while(p && st[p].nxt[c] == q){ st[p].nxt[c] = clone; p = st[p].link; } st[q].link = st[cur].link = clone; } } } void add_edge(int from,int to){ e[++cnt] = edge(head[from],to); head[from] = cnt; } void dfs(int now){ if(flag[now]) endpos[now] = 1; for(int i = head[now]; i; i = e[i].nxt){ int to = e[i].to; dfs(to); endpos[now] += endpos[to]; } } signed main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); sam_init(); scanf("%s",s+1);int n = strlen(s+1); for(int i = 1; i<=n; i++){ sam_extend(s[i] - 'a'); } for(int i=1; i<=sz; i++){ //构造 fail 树,获取 endpos add_edge(st[i].link,i); } dfs(1); int q; scanf("%lld",&q); while(q--){ int ans = 0; memset(vis,false,sizeof(vis)); scanf("%s",t+1);int m = strlen(t+1); for(int j=m+1; j<2*m; j++) t[j] = t[j - m]; int now = 1,len = 0; for(int i=1; i<=2*m-1; i++){ while(!st[now].nxt[t[i] - 'a']){ //暴力跳 fail 找到有 t[i] 的转移的边 now = st[now].link,len = st[now].len; if(now == 1) break; } if(st[now].nxt[t[i]-'a']) now = st[now].nxt[t[i] - 'a'],len++; else now = 1,len = 0; //没有转移也就是没有那么就回到最初状态 if(len > m){ //len > |t| 的情况 while(st[st[now].link].len >= m) now = st[now].link,len = st[now].len; } if(len >= m && !vis[now]){ //每个状态只被访问一次 ans += endpos[now]; vis[now] = true; } } printf("%lld\n",ans); } return 0; }
会发现我的板子就是直接复制的,所以其实板子并没有任何的含金量。
这篇关于【题解】后缀自动机(SAM)选做(22.8.11)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-03-29Gitlab 实现仓库完全迁移,包括所有提交记录、分支、标签
- 2024-03-28numpy moving average
- 2024-03-28lsp框架
- 2024-03-28in文件
- 2024-03-28ninoka nk 700
- 2024-03-28volatile java
- 2024-03-28netflix hystrix
- 2024-03-28landsat ndvi
- 2024-03-28变分法
- 2024-03-28FMZ股票实盘、模拟盘程序化交易实战--股票版DualThrust策略