2020-2021:teams:no_morning_training:weekly:week8
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:week8 [2020/07/24 17:31] 发源于 |
2020-2021:teams:no_morning_training:weekly:week8 [2020/07/29 09:01] (当前版本) shaco |
||
|---|---|---|---|
| 行 86: | 行 86: | ||
| 本周完全摸鱼 | 本周完全摸鱼 | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| - | 推荐一道AC自动机的题吧 | + | === 来源 === |
| - | [[2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机|文本生成器]] | + | [[https://www.luogu.com.cn/problem/P4052|p4052 文本生成器]] |
| + | === 标签 === | ||
| + | AC自动机 DP | ||
| + | === 题意 === | ||
| + | 给出一些模式串和一个长度，求出给定长度下至少包含一个给出的模式串的文本串数量。 | ||
| + | === 思路 === | ||
| + | 这道题可以通过计算不包含任何一个模式串的文本串数量间接求解。\\ | ||
| + | 主要是在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; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | === comment === | ||
| + | 还算是有点复杂的，当时调了一段时间。 | ||
2020-2021/teams/no_morning_training/weekly/week8.1595583106.txt.gz · 最后更改: 2020/07/24 17:31 由 发源于
