string - 有没有办法优化 KMP 算法以涉及我们正在比较的字符？

Question

我注意到 KMP 算法在发现 Haystack[a] 和 Needle[b] 不匹配时只是参考故障函数，但它从不查看 Needle[b] 是什么。如果我们考虑 Needle[b] 是什么，是否有可能使 KMP 更快？

Answer 1

您原则上可以更新 KMP，以便故障表查看导致不匹配的输入字符。但是，有一个问题是您这样做要花多少钱以及这样做会获得多少好处。

KMP 的优点之一是预处理步骤需要时间 O(n)，其中 n 是模式字符串的长度。不依赖于字符串由多少个字符组成（例如 Unicode、ASCII 等）。简单地构建一个表，将每个字符与在某些情况下要做什么相关联会对预处理步骤的运行时间产生负面影响。

话虽如此，还有其他算法确实可以查看针中不匹配的字符。例如，Boyer-Moore 算法确实会根据找到的不匹配字符来决定下一步搜索的位置，因此它的运行速度比 KMP 快得多。如果您好奇它在实践中是如何工作的，您可能想研究一下该算法。