专栏首页数据结构与算法P3808 【模版】AC自动机(简单版)

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 条评论
登录 后参与评论

相关文章

  • 关于scanf与cin哪个快的问题

    一开始入c++的时候成天跑cin,cout 直到有一天用cin,cout超时 才知道scanf比cin快的多 但是后来又听说加了ios::sync_with_s...

    attack
  • Topcoder SRM 563 Div1 500 SpellCards

    有\(n\)张符卡排成一个队列,每张符卡有两个属性,等级\(li\)和伤害\(di\)。 你可以做任意次操作,每次操作为以下二者之一:

    attack
  • P1629 邮递员送信(未完成)

    题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

    attack
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-4 使用函数求素数和

    其中函数prime当用户传入参数p为素数时返回1,否则返回0;函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

    C you again 的博客
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题4-6 水仙花数

    水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

    C you again 的博客
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack

扫码关注云+社区

领取腾讯云代金券