string - Rabin karp字符串匹配算法复杂度

Question

在 rabin 算法中取模如何帮助降低本地 horners 规则字符串匹配的复杂性。请任何人解释

Answer 1

我猜按照 Horners 规则，你的意思是将字符串视为某个基数中的数字 ("abcd"= 'a' * p^3 + 'b' * p^2 + 'c' * p^1 + 'd ' * p^0) 并将字符串与数字进行比较，通过 Rabin 算法，您的意思本质上是相同的，但对其他数字取模。

问题是使用 Horners 规则你只能比较短字符串——否则你会溢出(你可以使用大整数来避免它，但这就是你失去复杂性的地方。对应于长度为 n 的字符串的数字将有 O(n) 个数字，所以算术运算不会在 O(1) 中完成。

并且在 Rabin-Karp 算法中，与我们的字符串对应的数字将保持较小，因为我们将它们取模于其他数字。它可能会导致碰撞，但如果幸运的话，碰撞很少见。