字符串模式匹配算法简析(2)—— Rabin Karp 算法

前情提要 之前写过一篇:https://www.kmahyyg.xyz/archives/105 简要介绍了大学课本中常见的 KMP 和 BruteForce 子字符串模式匹配算法,同时根据 WikiPedia 的内容扩展了 Sunday 算法。 今天在完成 LeetCode 的过程中 https://leetcode.com/problems/implement-strstr 发现 builtin 的 strings 的库速度最快,引起了我的好奇。 本科阶段几乎都学过 KMP 算法,然而 KMP 算法的 next 数组的生成难于理解,生成算法也不是很方便,没有通用性、记忆的性价比也不够高。不论是实际应用还是面试,我想都不是一个好的选择。 常见的几个语言中: Java String 类中的 indexOf() 方法,C++ 的 strstr() 函数,使用了 O(n*m) 的暴力比较;Golang strings 包中的 Index() 方法中使用了下述 Rabin-Karp 算法,时间复杂度 O(n+m),同样没有使用 KMP。Golang 使用 R-K 配合上其对 Bytes 序列的优化,达成了较好的运算速度。 Rabin Karp 依赖 ——... » read more