本题是一道比较困难的多串匹配问题。
首先你需要了解如何用AC自动机或者Trie图解决一般的多串匹配问题。这里“一般”指的是只需要判断S中是否存在Keywords即可。
可以参考Trie图或者网上的资料。
在一般的Trie图中我们只需要标记出终结点即可，而本题需要计算每个终结点对应的最长匹配长度是多少。
这样对于S中的每一个字符S[i]，我们都可以求出以S[i]结尾是否有Keyword匹配。并且如果有，那么最长的长度是多少。
假设以S[i]结尾最长的匹配长度是l，那么显然S[i-l+1] ... S[i]都应该打星号。
这样我们就得到了一堆区间[a1, b1], [a2, b2], ... [ak, bk]，表示S[ai ... bi]应该被打星号。
最后我们要判断每个字符 S[0], S[1], ... S[|S|-1] 是不是要打星号，等价于判断i是不是被这些区间覆盖。而是一个经典的区间问题，我们可以通过将区间排序来迅速O(1)得出答案。
//递归调用 左 根 右 遍历 public class Solution { //双向链表的左边头结点和右边头节点 TreeNode leftHead = null; TreeNode rightHead = null; public TreeNode Convert(TreeNode pRootOfTree) { //递归调用叶子节点的左右节点返回null if(pRootOfTree==null) return null; //第一次运行时，它会使最左边叶子节点为链表第一个节点 Convert(pRootOfTree.left); if(rightHead==null){ leftHead= rightHead = pRootOfTree; }else{ //把根节点插入到双向链表右边，rightHead向后移动 rightHead.right = pRootOfTree; pRootOfTree.left = rightHead; rightHead = pRootOfTree; } //把右叶子节点也插入到双向链表（rightHead已确定，直接插入） Convert(pRootOfTree.right); //返回左边头结点 return leftHead; } }
可以告知第二组评测数据吗,纯kmp做的都ac了,ac自动机做的就是过不了第二组数据,反例也找不到
请问一下，纯kmp怎么AC的，我的只有90%。:(
我加了点差分过了，去学习下ac自动机来A这题