这是一道水题

给定几个特征串和几个字符串,求每个字符串中有那几个特征码

思路:

把每个特征串放到TRIE树里(上),用AC机挂着每个串跑一遍即可。但是会出现一种情况:若B串为A串子串,则可能出现没有匹配到B串的情况。比如 ABCD 和 BC,如果用不加修饰的AC机跑,会直接把ABCD匹配了,而BC在TRIE树的另一个分支上,没有访问。所以有3个解决办法:

1.在建树前用strstr确定每个串是否为另一个串的子串(O(N4)TLE)。因此改成KMP,复杂度O(N3),然而代码量很大。

注意到方案1使用的KMP实际上是对TRIE树每个树枝进行匹配,由此不难想到:

2. 在建树时递归沿着FAIL指针向树根寻找,如果FAIL指针指向的节点为一个特征串的结尾,则将此特征添加到原节点。使用vector可以通过此题。

3.注意到题目时间限制比较宽松,因此可以在AC自动机每寻找到一个节点时递归FAIL指针,操作通方案2.