一问题描述

在现代，谷歌、百度等搜索引擎走进了每个人的生活。

Wiskey 也希望将这个特性引入到他的图像检索系统中。

每个图像都有一个很长的描述，当用户健入一些关犍字来查找图像时，系统会将关键字与图像的描述进行匹配，并显示出匹配关犍字最多的图像。

为了简化问题，给你一个图像的描述，和一些关犍字，你应该告诉我有多少关犍字将匹配。

二输入和输出

1 输入

第 1 行将包含一个整数，表示后面将有多少个测试用例。

每个测试用例包含一个整数 n 表示关键字的数目，n 个关键字紧随其后。

每个关键字只包含 a 到 z，长度不超过 50。

最后一行是描述，长度不超过 1000000。

2 输出

打印描述中包含多少关键字。

三输入和输出样例

1 输入样例

1

5

she

he

say

shr

her

yasherhs

2 输出样例

3

四分析和设计

1 分析

在一个字符串中查询有多少个关键字出现，典型的多模匹配问题，可以采用 AC 自动机解决。

2 设计

a 将每个关键字插入到字典树中。

b 在字典树中添加失配指针，创建 AC 自动机。

c 在 AC 自动机中查询字符串包含多少个关键字。

五代码

package com.platform.modules.alg.alglib.hdu2222;import java.util.LinkedList;
import java.util.Queue;public class Hdu2222 {public static int K = 26;public String output = "";void init() // 初始化{superRoot = new node();root = new node();root.fail = superRoot;for (int i = 0; i < K; i++)superRoot.ch[i] = root;superRoot.count = -1;}private node superRoot;private node root;void insert(String str) // Trie 的插入{node t = root;int len = str.length();for (int i = 0; i < len; i++) {int x = str.charAt(i) - 'a';if (t.ch[x] == null)t.ch[x] = new node();t = t.ch[x];}t.count++;}void build_ac() {Queue<node> q = new LinkedList<>(); // 队列，BFS使用q.add(root);while (!q.isEmpty()) {node t;t = q.peek();q.poll();for (int i = 0; i < K; i++) {if (t.ch[i] != null) {t.ch[i].fail = t.fail.ch[i];q.add(t.ch[i]);} elset.ch[i] = t.fail.ch[i];}}}int query(String str) {int ans = 0;node t = root;int len = str.length();for (int i = 0; i < len; i++) {int x = str.charAt(i) - 'a';t = t.ch[x];for (node u = t; u.count != -1; u = u.fail) {ans += u.count;u.count = -1;}}return ans;}public String cal(String input) {int n;String str1;String str2;init();String[] line = input.split("\n");n = Integer.parseInt(line[0]);int count = 1;while (n-- > 0) {str2 = line[count++];insert(str2);}build_ac();str1 = line[count];output += query(str1) + "\n";return output;}
}class node {node fail;node ch[] = new node[Hdu2222.K];int count;node() {fail = null;for (int i = 0; i < ch.length; i++) {ch[i] = null;}count = 0;}
};