其实这个专题 NOIP 几乎不考
AC 自动机, 看起来是一个能让题目 AC 的东西, 但是事实并非如此
AC 自动机是解决多模式串与文本串匹配的问题
是 KMP+Trie 树的结合, 也是一个毒瘤算法
- Keywords Search
- link
此题是 AC 自动机的板子, 刚才说过 AC 自动机是解决匹配问题的, 这道题便如此
板子题, 记录结尾即可
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- inline int read()
- {
- int f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- int t,n;
- int bo[500005],tot,ch[500005][26];
- char str[1000001];
- void insert(char *str)
- {
- int u=1;
- int len=strlen(str);
- for(int i=0;i<len;i++)
- {
- int c=str[i]-'a';
- if(ch[u][c]==0) ch[u][c]=++tot;
- u=ch[u][c];
- }
- bo[u]++;
- return;
- }
- int nex[500005],que[500005];
- void bfs()
- {
- que[1]=1,nex[1]=0;
- int head=1,tail=1;
- while(head<=tail)
- {
- int t=que[head]; head++;
- for(int i=0;i<=25;i++)
- {
- if(ch[t][i]==0) ch[t][i]=ch[nex[t]][i];
- else{
- que[++tail]=ch[t][i];
- int v=nex[t];
- nex[ch[t][i]]=ch[v][i];
- }
- }
- }
- }
- int ans;
- void find(char *str)
- {
- int u=1,k;
- int len=strlen(str);
- for(int i=0;i<len;i++)
- {
- int c=str[i]-'a';
- k=ch[u][c],u=ch[u][c];
- while(k>1)
- {
- ans+=bo[k];
- bo[k]=0;
- k=nex[k];
- }
- }
- return;
- }
- int main()
- {
- t=read();
- while(t--)
- {
- ans=0;
- tot=1;
- memset(ch,0,sizeof(ch));
- memset(bo,0,sizeof(bo));
- for(int i=0;i<=25;i++) ch[0][i]=1;
- n=read();
- for(int i=1;i<=n;i++)
- {
- scanf("%s",str);
- insert(str);
- }
- bfs();
- scanf("%s",str);
- find(str);
- cout<<ans<<endl;
- }
- }
- View Code
玄武密码
link
此题求模式串在文本串前缀最大匹配长度
所以让文本串在 AC 自动机上走一遍, 用 flag 记录经过的点
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- inline int read()
- {
- int f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- int n,m,le[100001];
- char cx(char u)
- {
- if(u=='E') return '0';
- if(u=='S') return '1';
- if(u=='W') return '2';
- if(u=='N') return '3';
- }
- int fa[10000001],ch[1000001][4],tot;
- bool flag[1000001];
- char str[1110];
- int nex[1000010];
- int que[1000010];
- char s[10000010];
- int son[100001];
- void insert(char *str,int an)
- {
- int u=1;
- int len=strlen(str);
- le[an]=len;
- for(int i=0;i<len;i++)
- {
- int c=str[i]-'0';
- if(ch[u][c]==0) ch[u][c]=++tot,fa[tot]=u;
- u=ch[u][c];
- }
- son[an]=u;
- return;
- }
- void bfs()
- {
- nex[1]=0,que[1]=1;
- int head=1,tail=1;
- while(head<=tail)
- {
- int x=que[head];head++;
- for(int i=0;i<4;i++)
- {
- if(ch[x][i]==0) ch[x][i]=ch[nex[x]][i];
- else{
- que[++tail]=ch[x][i];
- nex[ch[x][i]]=ch[nex[x]][i];
- }
- }
- }
- return;
- }
- int ls;
- void find(char *s)
- {
- int u=1,k;
- for(int i=0;i<ls;i++)
- {
- int c=s[i]-'0';
- k=ch[u][c];
- while(k>1)
- {
- if(flag[k]) break;
- flag[k]=1;
- k=nex[k];
- }
- u=ch[u][c];
- }
- return;
- }
- int work(int an)
- {
- int u=son[an];
- for(int i=le[an];i>=1;i--)
- {
- if(flag[u]) return i;
- u=fa[u];
- }
- return 0;
- }
- int main()
- {
- memset(ch,0,sizeof(ch));
- tot=1;
- n=read(),m=read();
- scanf("%s",s);
- for(int i=0;i<4;i++) ch[0][i]=1;
- ls=strlen(s);
- for(int i=0;i<ls;i++) s[i]=cx(s[i]);
- for(int i=0;i<4;i++) ch[0][i]=1;
- for(int i=1;i<=m;i++)
- {
- scanf("%s",str);
- int l=strlen(str);
- for(int j=0;j<l;j++) str[j]=cx(str[j]);
- insert(str,i);
- }
- bfs();
- find(s);
- for(int i=1;i<=m;i++) printf("%d\n",work(i));//cout<<work(i)<<endl;
- }
- View Code
- Censoring
- link
也是让文本串在 AC 自动机上跑, 然后记录一下位置
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<stack>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- inline int read()
- {
- int f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- char str[1000011];
- int n;
- int ch[2600001][26],tot;
- char s[1000011];
- int que[2600001],nex[2600001];
- int bo[2600001];
- void insert(char *s)
- {
- int len=strlen(s);
- int u=1;
- for(int i=0;i<len;i++)
- {
- int c=s[i]-'a';
- if(ch[u][c]==0) ch[u][c]=++tot;
- u=ch[u][c];
- }
- bo[u]=len;
- return;
- }
- void bfs()
- {
- int head=1,tail=1;
- que[1]=1,nex[1]=0;
- while(head<=tail)
- {
- int x=que[head];head++;
- for(int i=0;i<26;i++)
- {
- if(ch[x][i]==0) ch[x][i]=ch[nex[x]][i];
- else{
- que[++tail]=ch[x][i];
- nex[ch[x][i]]=ch[nex[x]][i];
- }
- }
- }
- return;
- }
- int stk1[26000001],stk2[26000001];
- void find(char *str)
- {
- int u=1;
- int tot=0;
- int len=strlen(str);
- for(int i=0;i<len;i++)
- {
- int c=str[i]-'a';
- u=ch[u][c];
- stk1[++tot]=u;
- stk2[tot]=i;
- while(bo[u])
- {
- tot-=bo[u];
- u= stk1[tot];
- }
- }
- for(int i=1;i<=tot;i++) cout<<str[stk2[i]];
- cout<<endl;
- }
- int main()
- {
- tot=1;
- for(int i=0;i<26;i++) ch[0][i]=1;
- scanf("%s",str);
- n=1;
- for(int i=1;i<=n;i++)
- {
- scanf("%s",s);
- insert(s);
- }
- bfs();
- find(str);
- }
- View Code
单词 (待补此坑)
最短母串 (待补此坑)
病毒
link
此题是不让文本串在 AC 自动机上跑到每个模式串的末尾
所以想这个问题, 如果说你有无穷长度的文本串
在 AC 自动机上跑着, 但是不让他经过末尾
所以说这个图是有环的, AC 自动机不是因为节省时间直接相连 nex 吧, 所以好像这个叫做 fail 图
所以看一下在 AC 自动机中不经过每个字符串尾端是否有环即可
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- using namespace std;
- inline int read()
- {
- int f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- char s[900001];
- int tot,st[9000001];
- int ch[9000001][3];
- int n;
- int quee[3000001],nex[3000001];
- void insert(char *s)
- {
- int len=strlen(s),u=1;
- for(int i=0;i<len;i++)
- {
- int c=s[i]-'0';
- if(!ch[u][c]) ch[u][c]=++tot;
- u=ch[u][c];
- }
- st[u]=1;
- return;
- }
- void bfs()
- {
- int head=1,tail=1;
- quee[1]=1,nex[1]=0;
- while(head<=tail)
- {
- int x=quee[head];head++;
- for(int i=0;i<=1;i++)
- {
- if(ch[x][i]==0) ch[x][i]=ch[nex[x]][i];
- else{
- quee[++tail]=ch[x][i];
- nex[ch[x][i]]=ch[nex[x]][i];
- if(st[nex[ch[x][i]]]) st[ch[x][i]]++;
- }
- }
- }
- return;
- }
- int vis1[300011],vis2[300011];
- bool flag;
- void dfs(int f)
- {
- if(flag) return;
- vis2[f]=1;
- for(int i=0;i<=1;i++)
- {
- int s=ch[f][i];
- if(flag) return;
- if(st[s]) continue;
- if(vis2[s])
- {
- flag=1;
- cout<<"TAK";
- return;
- }
- if(flag) return;
- if(vis1[s]) continue;
- vis1[s]=1;
- dfs(s);
- }
- vis2[f]=0;
- }
- int main()
- {
- tot=1;
- n=read();
- for(int i=0;i<=1;i++) ch[0][i]=1;
- for(int i=1;i<=n;i++) scanf("%s",s),insert(s);
- bfs();
- flag=false;
- dfs(0);
- if(flag==0) cout<<"NIE";
- return 0;
- }
- /*
- 2
- 1
- 0
- */
- View Code
文本生成器
link
第一次在 AC 自动机上跑 dp
想一个问题, 如果这个有 m 长度的文本串符合条件的话, 他至少是一个模式的母串吧
你怎么去统计呢, 有可能是一个, 两个, 三个, 四个~~~
在数学上有一种想法是退而求进, 所以可以把这道题转换成有多少个无法模式串匹配的情况
这时候求的就是 0 了, 然后去拿总可能 - 这种可能便是答案
为什么说这一道题是 dp 呢, 因为满足 dp 的思想了
dp[i] 为长度为 i 有多少个
但是无法往前推
所以再加一维, 加什么呢
很容易想到是访问在哪个节点吧
所以 dp 模型就已经定下来了
dp[i][j] 表示现在长度为 i, 节点是 j 共有多少个串
AC 自动机有什么用呢, 其实就是建图有用
将字符串转换成一张图
不让他走末尾节点
所以现在就有一个要注意的坑点了
*** 当你找到一点 x, 若此点的 nex 是一个字符串的结尾, 所以这个 x 其实就是一个病毒了
其实就是每人对 nex 理解了
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define mod 10007
- using namespace std;
- inline long long read()
- {
- long long f=1,ans=0;char c;
- while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
- while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
- return f*ans;
- }
- long long n,m,tot,u,ch[900001][26],bo[900001];
- char s[3000001];
- void insert(char *s)
- {
- long long len=strlen(s),u=1;
- for(long long i=0;i<len;i++)
- {
- long long c=s[i]-'A';
- if(!ch[u][c]) ch[u][c]=++tot;
- u=ch[u][c];
- }bo[u]=1;
- return;
- }
- long long que[3000001],nex[3000001];
- void bfs()
- {
- long long head=1,tail=1;
- que[1]=1,nex[1]=0;
- while(head<=tail)
- {
- long long xx=que[head];head++;
- for(long long i=0;i<26;i++)
- {
- if(ch[xx][i]==0) ch[xx][i]=ch[nex[xx]][i];
- else{
- que[++tail]=ch[xx][i];
- nex[ch[xx][i]]=ch[nex[xx]][i];
- bo[ch[xx][i]]|=bo[ch[nex[xx]][i]];
- }
- }
- }
- return;
- }
- long long dp[151][300001];
- int main()
- {
- for(long long i=0;i<26;i++) ch[0][i]=1;
- tot=1;
- n=read(),m=read();
- for(long long i=1;i<=n;i++)
- {
- scanf("%s",s);
- insert(s);
- }
- bfs();
- dp[0][1]=1;
- for(long long i=1;i<=m;i++)
- for(long long j=1;j<=tot;j++)
- for(long long z=0;z<26;z++)
- if(!bo[ch[j][z]]) dp[i][ch[j][z]]+=dp[i-1][j],dp[i][ch[j][z]]%=mod;
- long long ans=0;
- for(long long i=1;i<=tot;i++) ans+=dp[m][i],ans%=mod;
- long long sum=1;
- for(long long i=1;i<=m;i++) sum*=26,sum%=mod;
- cout<<(sum-ans+mod)%mod;
- }
- View Code
来源: https://www.cnblogs.com/si-rui-yang/p/9709479.html