我到处搜索，但没有找到关于袋鼠方法的良好、清晰的解释。只是我找到了一些ppts，但对我来说没用，因为我以前没有读过袋鼠方法。那些ppts是为了修改袋鼠方法。
如果有人可以提供有关袋鼠方法的阅读材料或视频教程链接，这将是一个很大的帮助。
提前谢谢
问问题
730 次
1 回答
4
令 T=t1t2...tn, P=p1p2...pm
k=# 允许的错误
预处理 T$1P$2 的后缀树 [时间：O(nlog|Sigma| 通过 Weiner 算法构造后缀树) Sigma 是语言。
在我们刚刚创建的树上预处理 LCA。[时间：O(n)]
在所有节点上运行并在每个节点上写入它距根的高度。[时间：我们有 O(n) 个节点]
遍历所有后缀（=leaves）并为每个后缀 Si 初始化一个错误计数器并查询 h1=height(LCA(Si,P))，如果 h>=m 我们将 i 添加到解决方案中，否则：err++ 并且如果err<=k 继续检查 h2=height(LCA(Si[h1+1,n],P[h1+1,m]))。
[时间：遍历所有后缀 => O(n)，对于每个后缀运行最多 k+1 次 => O(kn)]
希望这会有所帮助...
衬套
于 2012-08-26T14:16:02.027 回答