Nit*_*tty 2 c java string integer time-complexity
就时间复杂度而言，字符串匹配和整数匹配有何不同？
我问这个特别是关于 Rabin Karp 算法。为什么计算每个子字符串的哈希码并检查其与给定搜索字符串的哈希码是否相等比仅检查任何子字符串是否与给定字符串匹配的简单方法更快？
通常，在设计算法时，您假设机器模型是这样的，即可以在恒定时间内比较任意两个整数（适合机器字）。由于字符串可能比单个机器字长，因此比较两个长度为 n 的字符串将需要 O(n) 次比较。因此，比较两个机器字比比较两个字符串要快。
Rabin-Karp 算法是有效的，因为它使用哈希码的比较来最小化实际需要进行昂贵的字符串比较的次数。具体来说，Rabin-Karp 只将一个子字符串与模式字符串进行比较，如果该子字符串与原始模式字符串具有相同的哈希码，则消除了许多不必要的工作。
希望这可以帮助！