2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机 [2020/07/24 09:57] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机 [2020/07/26 19:10] (当前版本) shaco |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| AC自动机可以说是KMP的进阶版，支持多个模式串在目标串中的查询。\\ | AC自动机可以说是KMP的进阶版，支持多个模式串在目标串中的查询。\\ | ||
| 复杂度为$O((N+M)\times L)$。\\ | 复杂度为$O((N+M)\times L)$。\\ | ||
| - | \textcolor{blue}{文本生成器在下面} | + | |
| ====== 思路 ====== | ====== 思路 ====== | ||
| 首先对模式串进行trie树的构建。\\ | 首先对模式串进行trie树的构建。\\ | ||
| 行 256: | 行 256: | ||
| for(int i=1;i<=n;i++) | for(int i=1;i<=n;i++) | ||
| printf("%d\n",vist[pos[i]]); | printf("%d\n",vist[pos[i]]); | ||
| - | return 0; | ||
| - | } | ||
| - | </code> | ||
| - | </hidden> | ||
| - | ===== 洛谷 p4052 [JSOI2007] 文本生成器 ===== | ||
| - | 给出一些模式串和一个长度，求出给定长度下至少包含一个给出的模式串的文本串数量。 | ||
| - | |||
| - | 这道题可以通过计算不包含任何一个模式串的文本串数量间接求解。\\ | ||
| - | 主要是在Trie树上运用dp。 | ||
| - | |||
| - | 在这里我想做题的人需要对文本串在Trie树上匹配的过程有一个直观而清晰的认识——匹配到当前的树上的位置代表一切其fail一串上的均可以匹配，但以该点为fail的位置不能被匹配。\\ | ||
| - | |||
| - | 运用dp，dp[i][j]表示 长度为i、结点序号为j的位置不包含任何一个模式串的文本串数量。\\ | ||
| - | 状态转移方程为：dp[i+1][son[j][k]]+=dp[i][j] (!flag[son[j][k])\\ | ||
| - | 这里面需要注意的是，如果一个结点是一个模式串的末尾，那么以其为fail关系的子孙的结点都要标记flag，原因如上。 | ||
| - | <hidden code> | ||
| - | <code cpp> | ||
| - | #include<cstdio> | ||
| - | #include<queue> | ||
| - | using namespace std; | ||
| - | int n,m,tot=1,dp[6005][105],mod=10007; | ||
| - | char s[105]; | ||
| - | struct unit{int s[27],fail,flag;}T[6005]; | ||
| - | void Insert() | ||
| - | { | ||
| - | int root=1,id; | ||
| - | for(int i=0;s[i];i++) | ||
| - | { | ||
| - | id=s[i]-65; | ||
| - | if(!T[root].s[id]) | ||
| - | T[root].s[id]=++tot; | ||
| - | root=T[root].s[id]; | ||
| - | } | ||
| - | T[root].flag=1; | ||
| - | } | ||
| - | void get_fail() | ||
| - | { | ||
| - | for(int i=0;i<26;i++) | ||
| - | T[0].s[i]=1; | ||
| - | T[1].fail=0; | ||
| - | queue<int>q; | ||
| - | q.push(1); | ||
| - | int m=1,head; | ||
| - | while(m--) | ||
| - | { | ||
| - | head=q.front(); | ||
| - | q.pop(); | ||
| - | for(int i=0,v,fafail;i<26;i++) | ||
| - | { | ||
| - | v=T[head].s[i]; | ||
| - | fafail=T[head].fail; | ||
| - | if(!v) T[head].s[i]=T[fafail].s[i]; | ||
| - | else | ||
| - | { | ||
| - | T[v].fail=T[fafail].s[i]; | ||
| - | T[v].flag|=T[T[v].fail].flag; | ||
| - | q.push(v); | ||
| - | m++; | ||
| - | } | ||
| - | } | ||
| - | } | ||
| - | } | ||
| - | int main() | ||
| - | { | ||
| - | scanf("%d%d",&n,&m); | ||
| - | for(int i=1;i<=n;i++) | ||
| - | { | ||
| - | scanf("%s",s); | ||
| - | Insert(); | ||
| - | } | ||
| - | get_fail(); | ||
| - | dp[1][0]=1; | ||
| - | for(int i=1;i<=m;i++) | ||
| - | for(int j=1;j<=tot;j++) | ||
| - | for(int k=0;k<26;k++) | ||
| - | if(!T[T[j].s[k]].flag) | ||
| - | dp[T[j].s[k]][i]=(dp[T[j].s[k]][i]+dp[j][i-1])%mod; | ||
| - | int ans=1; | ||
| - | for(int i=26,j=m;j;j>>=1,i=(i*i)%mod) | ||
| - | if(j&1) | ||
| - | ans=(ans*i)%mod; | ||
| - | for(int i=1;i<=tot;i++) | ||
| - | ans=(ans-dp[i][m]+mod)%mod; | ||
| - | printf("%d",ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/ac自动机.1595555871.txt.gz · 最后更改: 2020/07/24 09:57 由 shaco
