题意:
问母串中出现多少个模式串
注意ac自动机的节点总数
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
inline int Max(int a,int b){return a>b?a:b;}
inline int Min(int a,int b){return a>b?b:a;}
int ANS; #define N 1000010
#define maxnode 250001
#define sigma_size 26 struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int last[maxnode];
int f[maxnode];
int sz;
void init(){
sz=1;
memset(ch,0,sizeof(ch));
memset(val, 0, sizeof(val));
memset(f,0,sizeof(f));
memset(last,0,sizeof(last));
}
int idx(char c){
return c-'a';
}
void print(int j){
if(j){
printf("%d: %d\n", j, val[j]);
print(last[j]);
}
}
void Creat(char *s){
int u = 0, len = strlen(s);
for(int i = 0;i < len;i++){
int c = idx(s[i]);
if(!ch[u][c])
ch[u][c] = sz++; u = ch[u][c];
}
val[u] ++;
}
void getFail(){
queue<int> q;
for(int i = 0; i<sigma_size; i++)
if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()){
int r = q.front(); q.pop();
for(int c = 0; c<sigma_size; c++){
int u = ch[r][c];
if(!u)continue;
q.push(u);
int v = f[r];
while(v && ch[v][c] == 0) v = f[v]; //沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环
f[u] = ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
}
void find(char *T){
int len = strlen(T), j = 0;
for(int i = 0; i < len; i++){
int c = idx(T[i]);
while(j && ch[j][c]==0) j = f[j];
j = ch[j][c]; int temp = j;
while(temp && val[temp]){
ANS += val[temp];
val[temp] = 0;
temp = f[temp];
}
}
}
};
Trie ac;
char S1[N];
int Slen; void InputString(){
scanf("%s",S1);
Slen = strlen(S1);
S1[Slen]='\0';
}
int main(){ int T,i,j,n;scanf("%d",&T); while(T--){
ac.init();
scanf("%d",&n);
while(n--){
scanf("%s",S1);
ac.Creat(S1);
}
ac.getFail();
InputString();
ANS = 0;
ac.find(S1); printf("%d\n",ANS); }
return 0;
}
/*
1
5
she
he
say
shr
her
yasherhs ans:
3 */
HDU 2222 AC自动机 裸题的更多相关文章
-
HDU 2222 AC自动机模板题
题目: http://acm.hdu.edu.cn/showproblem.php?pid=2222 AC自动机模板题 我现在对AC自动机的理解还一般,就贴一下我参考学习的两篇博客的链接: http: ...
-
hdu 2222(AC自动机模版题)
Keywords Search Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others ...
-
HDU 2222 AC自动机模版题
所学的AC自动机都源于斌哥和昀神的想法. 题意:求目标串中出现了几个模式串. 使用一个int型的end数组记录,查询一次. #include <cstdio> #include <c ...
-
HDU 3065 AC自动机 裸题
中文题题意不再赘述 注意 失配数组 f 初始化一步到位 #include <stdio.h> #include <string.h> #include <queue&g ...
-
HDU 2896 AC自动机 裸题
中文题题意不再赘述 注意字符范围是可见字符,从32开始到95 char c - 32 #include <stdio.h> #include <string.h> #inclu ...
-
HDU 2222 AC自动机(模版题)
Keywords Search Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others ...
-
Keywords Search HDU - 2222 AC自动机板子题
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc. Wiskey al ...
-
AC自动机裸题
HDU 2222 Keywords Search 模板题.对模式串建立AC自动机然后在trie树上找一遍目标串即可. # include <cstdio> # include <cs ...
-
HDU 3065 (AC自动机模板题)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3065 题目大意:多个模式串,范围是大写字母.匹配串的字符范围是(0~127).问匹配串中含有哪几种模 ...
随机推荐
-
Unplugging一个PDB
Unplugging一个PDB Unplugging一个pdb不等于remove一个pdb Unplugging一个pdb会创建一个对应的xml文件,借助该xml文件可以将其添加到其他的cdb pdb ...
-
Oracle dblink 使用详解
1.dblink简介 dblink(Database Link)数据库链接就是数据库的链接,跨本地数据库 2.使用语法详解 基本语法 CREATE [SHARED][PUBLIC] database ...
-
猎豹上市(猎豹的广告收入中有70%来自BAT三家公司,总收入中有58%来自BAT)
发表日期: 2014 年 5 月 9 日 From 网易专题 文/赵楠 村里那点儿事 猎豹移动上市之夜,我挺激动. 激动除了因为有好朋友在这家公司外,也因为猎豹移动在历史上的几次起承转合非常不易,在巨 ...
-
百度地图LV1.5实践项目开发工具类bmap.util.jsV1.0
/** * 百度地图使用工具类-v1.5 * * @author boonya * @date 2013-7-7 * @address Chengdu,Sichuan,China * @email b ...
-
C# 基础问答
1.静态变量和非静态变量的区别? 2.const 和 static readonly 区别? 3.extern 是什么意思? 4.abstract 是什么意思? 5.internal 修饰符起什么作用 ...
-
Eureka服务端源码流程梳理
一.简述 spring cloud三步走,一导包,二依赖,三配置为我们简化了太多东西,以至于很多东西知其然不知其所以然,了解底层实现之后对于一些问题我们也可以快速的定位问题所在. spring clo ...
-
deeplabv3+ demo测试图像分割
#!--*-- coding:utf-8 --*-- # Deeplab Demo import os import tarfile from matplotlib import gridspec i ...
-
格雷码(Gray code)仿真
作者:桂. 时间:2018-05-12 16:25:02 链接:http://www.cnblogs.com/xingshansi/p/9029081.html 前言 FIFO中的计数用的是格雷码, ...
-
CyberArticle(eLib电子图书馆)网文快捕
CyberArticle (网文快捕)是一款知识管理软件,主要致力于网页的保存和后期管理.CyberArticle (网文快捕)主要功能,就是收集和整理网页.利用CyberArticle (网文快捕) ...
-
【C#】时间日期格式转换:long和DateTime相互转换
// DateTime --> long public static long ConvertDateTimeToLong(DateTime dt) { DateTime dtStart = T ...