hiho一下第218周《Keywords Filter》题目分析

6
0

《Keywords Filter》题目分析

本题是一道比较困难的多串匹配问题。

首先你需要了解如何用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)得出答案。

  • 可以告知第二组评测数据吗,纯kmp做的都ac了,ac自动机做的就是过不了第二组数据,反例也找不到

  • 请问一下,纯kmp怎么AC的,我的只有90%。:(

  • 我加了点差分过了,去学习下ac自动机来A这题

  • 添加评论
  • reply

3 answer(s)

0

//递归调用 左 根 右 遍历 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; } }

0

构造Trie的复杂度是O(10000 * 1000)?这样对于极端情况其实处理不了吧?

  • 1000*100000也就一亿而已嘛,其实是可以接受的

  • 字符串长度总和只有1e5

  • 添加评论
  • reply
0

有AC自动机的做法分享一下吗?

write answer 切换为英文 切换为中文


转发分享