子字符串查找 ——Rabin-Karp算法
求字符串的连续子串，如果传统的散列法复杂度很高。而Rabin-Karp算法的思路是 将字符串每个 字符 a~z 看作 0~25 组成的 26 进制的数。并且在计算 每个位置长度 为 n 的连续子串的散列值时 可以使用 除留余法 方式 将散列的复杂度降低为 O(1)
例题
最长重复子串
这个题也可以用 动态规划做，dp 设置为 字符串1 前 i 个 和 字符串2 前 j 个的子串的最长后缀长度。通过 两层遍历即可完成。
但是使用 二分查找 + hash 法 复杂度会更低（前提是 hash 使用Rabin-Karp算法散列，保证散列的复杂度为O(1)）