首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P3808 【模版】AC自动机(简单版)

P3808 【模版】AC自动机(简单版)

作者头像
attack
发布2018-04-12 14:43:57
6370
发布2018-04-12 14:43:57
举报

题目背景

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

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

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

题目描述

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

输入输出格式

输入格式:

第一行一个n,表示模式串个数;

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

下面一行一个文本串。

输出格式:

一个数表示答案

输入输出样例

输入样例#1:

2
a
aa
aa

输出样例#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 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-07-06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目背景
  • 题目描述
  • 输入输出格式
  • 输入输出样例
  • 说明
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档