[hdu2222] Keywords Search

Description

给定 \(n\) 个长度不超过 \(50\) 的由小写英文字母组成的单词准备查询，以及一篇长为 \(m\) 的文章，问：文中出现了多少个待查询的单词。多组数据。

Input

第一行一个整数 \(T\)，表示数据组数；
对于每组数据，第一行一个整数 \(n\)，接下去 \(n\) 行表示 \(n\) 个单词，最后一行输入一个字符串，表示文章。

Output

对于每组数据，输出一个数，表示文中出现了多少个待查询的单词。

Sample Input

1
5
she
he
say
shr
her
yasherhs

Sample Output

3

Hint

对于全部数据，\(1\le n\le 10^4,1\le m\le 10^6\)。

题解

AC自动机模板题

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int Size=26,Maxn=500005;
struct Trie{
	int son[Maxn][Size],fail[Maxn],cnt[Maxn];
/*	son[i][j]存放 父节点的下标为i 的子节点字符为j的下标
	fail[i]下标为i的节点如果失配放回的下标
	cnt[i]从根节点到下标为i的节点所构成的模式串的个数
*/	int id;
	Trie(){id=0;}//构造函数
	int Newnode()//新建一个节点
	{
		for(int i=0;i Q;
	void Build()//构建Fail指针
	{
		while(!Q.empty()) Q.pop();
		fail[0]=0;
		for(int i=0;i
题解AC自动机HDU字符串

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

题解 Count on a tree II/【模板】树分块

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

HttpURLConnection发送中文乱码问题解决

标签