首页 > 代码库 > P3808 【模版】AC自动机（简单版）
P3808 【模版】AC自动机（简单版）
题目背景
这是一道简单的AC自动机模版题。
用于检测正确性以及算法常数。
为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。
题目描述
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
输入输出格式
输入格式：
第一行一个n，表示模式串个数；
下面n行每行一个模式串；
下面一行一个文本串。
输出格式：
一个数表示答案
输入输出样例
输入样例#1：
2aaaaa
输出样例#1：
2
说明
subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；
也是模板，没什么么好说的，
只不过每次更新的时候是++，而不是=1！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #include<map> 8 using namespace std; 9 const int MAXN=1000001; 10 void read(int &n) 11 { 12 char c=‘+‘;int x=0;bool flag=0; 13 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;} 14 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-48;c=getchar();} 15 flag==1?n=-x:n=x; 16 } 17 char s[MAXN]; 18 char text[MAXN]; 19 int n; 20 int ans=0; 21 struct AC_Automata 22 { 23 int sz; 24 int ch[MAXN][26];//trie树 25 int val[MAXN];// 记录是否有单词 26 int last[MAXN]; 27 int f[MAXN]; 28 int sigma_sz; 29 void Init() 30 { 31 memset(ch[0],0,sizeof(ch[0])); 32 sz=1; 33 sigma_sz=26; 34 } 35 int idx(char c) 36 { 37 return c-‘a‘; 38 } 39 void Insert(char *s,int pos) 40 { 41 int l=strlen(s); int now=0; 42 for(int i=0;i<l;i++) 43 { 44 int c=idx(s[i]); 45 if(!ch[now][c]) 46 { 47 memset(ch[sz],0,sizeof(ch[sz])); 48 val[sz]=0; 49 ch[now][c]=sz++; 50 } 51 now=ch[now][c]; 52 } 53 val[now]++;//一个单词的结束 54 } 55 void getfail() 56 { 57 f[0]=0; 58 queue<int>q; 59 for(int i=0;i<sigma_sz;i++) 60 { 61 int u=ch[0][i]; 62 if(u)// 此处有单词出现 63 { 64 f[u]=0;// 连向根节点 65 q.push(u); 66 last[u]=0;// 上一个出现的单词一定是根节点 67 // 上面两条语句没什么卵用，只是为了帮助理解AC自动机的含义 68 } 69 } 70 while(!q.empty()) 71 { 72 int p=q.front();q.pop(); 73 for(int i=0;i<sigma_sz;i++) 74 { 75 int u=ch[p][i]; 76 if(!u)//没有孩子 77 { 78 ch[p][i]=ch[f[p]][i];// 补上一条不存在的边，减少查找次数 79 continue; 80 } 81 q.push(u); 82 int v=f[p];// 找到它的失陪指针 83 f[u]=ch[v][i];//因为我们在上面补上了一条不存在边，所以他一定存在孩子 84 last[u]=val[f[u]] ? f[u] : last[f[u]]; 85 //判断下是不是单词结尾 是， 不是 86 } 87 } 88 } 89 int ok(int pos) 90 { 91 if(val[pos]) 92 { 93 ans+=val[pos]; 94 val[pos]=0; 95 ok(last[pos]); 96 } 97 } 98 void find(char *s)// 查找模式串 99 {100 int l=strlen(s);101 int j=0;// 当前节点的编号102 for(int i=0;i<l;i++)103 {104 int c=idx(s[i]);105 while(j&&!ch[j][c]) 106 j=f[j];// 顺着失配边走107 j=ch[j][c]; // 取到儿子108 if(val[j]) 109 ok(j);// 找到一个单词110 else if(last[j]) 111 ok(last[j]);// 当前节点不行就看看上一个单词出现的位置行不行 112 } 113 }114 }ac;115 int main()116 {117 scanf("%d",&n);118 ac.Init();119 for(int i=1;i<=n;i++)120 {121 scanf("%s",s);122 ac.Insert(s,i);123 }124 ac.getfail();125 scanf("%s",text); 126 ac.find(text);127 printf("%d\n",ans);128 return 0;129 }
P3808 【模版】AC自动机（简单版）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。