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

题目背景

这是一道简单的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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

[快学Python3]数据结构与算法-二分查找

概述 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。 其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁...

2169
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3175
来自专栏有趣的Python

9-玩转数据结构-线段树

上一章我们介绍了堆,这一章我们介绍一种新的树结构,线段树(区间树) Segment Tree

2934
来自专栏Java开发者杂谈

遍历算法(1)

遍历算法主要用在在处理迷宫问题,图,最短路径,以及枚举所有可能等问题上。下面我们通过一个简单的例子,来入门深度优先和广度优先算法: 1 package co...

3566
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(一)

曾经做过的40道程序设计课后习题总结(一) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询...

3418
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

6105
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

1612
来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

3224
来自专栏开源优测

[快学Python3]数据结构与算法-二分查找

概述 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。 其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁...

3205
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3655

扫码关注云+社区

领取腾讯云代金券