题目背景

通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。

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


题解

在通常就没什么人认真听的集训里,qwerta刚撸完一把Win7原装的扫雷,舒适的抬起头,正好对上了老师讲fail树的眼神。

所以是懂一丢丢手推方法的。

建议大家先构造点小数据手推,像是什么在$her,him,he,his,she$上匹配$shehisher$之类的。

网上教程也蛮多,就不画图了。(懒

其实是自己也推不蛮清楚

然后是教材QAQ yyb大佬的博客

总之,AC自动机就是在trie树上bfs一下然后乱搞,可以理解为trie上的KMP叭。

自己都不怎么会,就不讲这个东西了QAQ

 #include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define R register
const int MAXL=1e6+;
char s[MAXL];
struct emm{
int fail;
int nxt[];
int tag;
}AC[MAXL];//Tree结构体
queue<int>q;//get_fail的时候用的queue
int main()
{
//freopen("a.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(false);cout.tie(false);
int n;
cin>>n;
int tot=;
//trie
while(n--)
{
cin>>s;
int len=strlen(s);
int now=;//now表示当前的节点编号
for(R int i=;i<len;++i)
{
if(!AC[now].nxt[s[i]-'a'])//如果当前节点没有这个儿子
AC[now].nxt[s[i]-'a']=++tot;//就造个儿子
now=AC[now].nxt[s[i]-'a'];//now跳到这个儿子上
}
AC[now].tag++;//now最后在的地方是这个模式串的结束点,标记一下
}
//get_fail
{
//首先把跟0号节点相连的点处理一下
for(R int i=;i<;++i)
{
if(AC[].nxt[i])//如果这个儿子存在
{
AC[AC[].nxt[i]].fail=;//把fail指向0号节点(其实默认就是0啊QAQ
q.push(AC[].nxt[i]);//把这个儿子push进去
}
}
while(!q.empty())
{
int x=q.front();q.pop();//取点
for(R int i=;i<;++i)
{
if(AC[x].nxt[i])//如果这个儿子存在
{
AC[AC[x].nxt[i]].fail=AC[AC[x].fail].nxt[i];//敲重点!!!
//这个儿子的fail,等于这个节点fail的儿子 会手推就能懂叭QAQ
q.push(AC[x].nxt[i]);//push进去
}
else
AC[x].nxt[i]=AC[AC[x].fail].nxt[i];//这里直接把nxt指向了fail的对应儿子
}
}
}
//run
cin>>s;
long long ans=;
int len=strlen(s);
int now=;//now表示当前节点编号
for(R int i=;i<len;++i)
{
now=AC[now].nxt[s[i]-'a'];//往下走一层(因为之前直接把空的nxt往fail指了,所以不需要通常的while跳fail
//大概就是Trie图和Trie树的区别了叭
for(R int t=now;t&&AC[t].tag!=-;t=AC[t].fail)//从这个点开始暴力跳fail,找匹配
{
ans+=AC[t].tag;
AC[t].tag=-;//这是个剪枝
}
}
cout<<ans;
return ;//撒花
}

然后吐槽一下咕咕的数据,之前有一大段把$now$和$i$混用了,结果还过了一个点(???

最新文章

  1. 在Thinkphp中使用AJAX实现无刷新分页
  2. SQL Server锁定【2015.12.17】
  3. Renderer.materials
  4. 双数组Trie树 (Double-array Trie) 及其应用
  5. poj4474 Scout YYF I(概率dp+矩阵快速幂)
  6. YII 1.0 隐藏单入口index.php 设置路由与伪静态
  7. ALTER TABLE SWITCH&#39; statement failed. The table x&#39; is partitioned while index &#39;x&#39; is not partitioned.
  8. [LeetCode] String Compression 字符串压缩
  9. html_javascript
  10. Spring boot 之自动生成API文档swagger2
  11. 觉得一篇讲SPFA还不错的文章
  12. Java复习总结——数据类型
  13. php 腾讯地图和百度地图的相互转换
  14. 无实体反序列化Json
  15. 4.数码相框-freetype多行显示,居中显示
  16. Android-Java-对象在内存中的简单关系图
  17. 分享一下个人学PS的过程
  18. c# 自定义类型的DataBindings
  19. php---截取描述方法
  20. mustache语法

热门文章

  1. Delphi TScrollBar 用于滚动窗口、组件内容
  2. [反汇编练习] 160个CrackMe之029
  3. hibernate的注解装配
  4. 关于C++ 命名空间Namespace 的解析
  5. Sencha Touch 之初接触
  6. 使用HtmlUnit登录百度
  7. 【转载】ASP和ASP.NET根本区别
  8. JS计算网页停留时间
  9. 设置Activity进入退出动画
  10. MVC入门——删除页