-1

我理解使用见证表算法的长度为 n 的文本 T 和长度为 m 的模式 P 的模式匹配算法是线性的。

我也知道如何在 m^2 时间内构建见证表，但是有一个 O(m) 的算法来构建我不理解的表。

请帮忙。

4

2 回答 2

2

也许你的意思是第一 部分第二部分 - 正确性

作者：Amihood Amir 计算机科学教授。

（这个数据不是我的）。

于 2012-08-28T20:06:45.857 回答
1

你最好看这里

有关于 KMP 算法和运行时分析的解释。

于 2012-08-24T10:11:29.947 回答