当前位置:首页 > 字符串 > AC自动机 > 正文
SSOJ2759KeywordsSearch
1666+

题目大意:n个单词和一篇长度为m的文章,请问有多少个单词在文章中程序过?

题目描述

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

输入

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

输出

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

提示

样例输入

1
5
she
he
say
shr
her
yasherhs

样例输出

3

对于全部数据,1n104,1m106

解题思路

一个字符串,跟多个字符串进行匹配,可以使用AC自动机:首先对单词建立Trie树,然后根据KMP的原理,预处理每一条链的最长公共前后缀——匹配不成功,往回退到哪里?保存到p数组。

因为长度大退到长度小,所以应该按照深度从小到大处理,即使用广搜。

最后匹配的时候,可能出现单词包含现象,因此匹配的最长公共前后缀,还需要继续往回找,看一下短一点的公共前后缀是否是单词,此处可以记忆化,否则往回退的次数约单词长度。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ2759KeywordsSearch:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!