在rabin算法中取模如何帮助降低本地角规则字符串匹配的复杂度。谁来解释一下
我猜根据Horners规则，你的意思是将字符串作为某种基数的数字("abcd" = 'a' * p^3 + 'b' * p^2 + 'c' * p^1 + 'd' * p^0)并将字符串作为数字进行比较，而通过Rabin算法，你的意思是本质上相同的事情，但对其他数字取模。
问题是使用霍纳斯规则，你只能比较短的字符串——否则你会溢出(你可以使用大整数来避免它，但这是你损失复杂性的地方。与长度为n的字符串相对应的数将有O(n)个数字，因此算术运算不会在O(1)中进行。
在Rabin-Karp算法中，对应于我们的字符串的数将保持较小，因为我们对其他数取模。它可能会导致碰撞，但如果我们足够幸运，碰撞是非常罕见的。