首页 > > 程序设计 > C/C++ >

P3808 【模版】AC自动机（简单版）

2018-06-17 22:15:55来源：未知阅读 ()

题目背景

这是一道简单的AC自动机模版题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

2
a
aa
aa

输出样例#1：

说明

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 }