程序设计在线评测(Online Judge)


问题 1027. -- 2011市赛题:Forbidden Words

1027: 2011市赛题:Forbidden Words

时间限制: 3 Sec  内存限制: 128 MB
提交: 28  解决: 3
[提交][状态][讨论版]

题目描述

There are many Forbidden Words(FW) in internet searching. Now I have the FW list and a passage, I want to find the longest substring that contain none FW.

输入

The first line contains an integer T (T<=100) indicating the number of test cases.

For each test case, the first line contain two integers n , m(0 < n <= 100000 , 0 <= m <= 1000)indicating the length of the passage and the number of the FW.

The next line contain the passage.

The next n line each contain a FW, the length of the FW not exceed 100.

The passage and the FW only contain capital letter.

输出

Output the length of the longest substring that contain none FW.

样例输入

2
39 3
IDONTNEEDSEXTHEGOVERMENTFUCKSMEEVERYDAY
SEX
GOVERMENT
FUCK
10 1
AAAAAAAAAA
AAA

样例输出

14
2

提示

设计算法:AC自动机

先建立trie,然后用AC自动机建立字符间的转移关系O(m*length*26)

解法1.

当匹配到敏感词后,要退到当前最短敏感词的第二位再进行匹配,但是如果每次都进行匹配的话,复杂度是O(n*length),会超时

我们可以在AC自动机建立后先把每个敏感词第二位开始匹配到达的位子预处理出来,之后匹配到敏感词就只需要O(1)的时间转移了

解法2.

先找出所有敏感词的位子,标记出以每个点为结尾匹配的最短敏感词,然后现行扫描


最后总复杂度O(n) + O(m*length*26)

来源

[提交][状态][讨论版]