# ⚡🏡🗝

我曾经以不正确的姿势学习研究了 KMP，但是被众说纷纭文章搞头脑迷糊了。看着别人撤了一堆的名词术语，又是动态规划，又是状态图，又是状态转换什么的，别人就是懂得多。感觉真是后悔学了中文，因为每个字我都懂，但就是不清楚别人在说什么😂

我觉得 KMP 搜索算法应该有更好的学习姿势，不需要扯概念扯术语，只需要直觉，Algorithm Visualizer 也许是一个可以在直觉上增加理解的好工具。

代码仓库可以通过以下链接或克隆获取：

    git clone git@github.com:jimboyeah/jitter_search.git

    git clone https://github.com/jimboyeah/jitter_search.git

以上是学习库 Algorithms.md 分类文档中关于字符串搜索算法的部分，因为有离线整理资料的习惯，只会挑选部分公开发布。使用的工具是 Sublime Text + Git，感谢作者的共享软件，真的非常高效。

# 🚩 Violent Search 暴力搜索算法

暴力搜索算法，Brute Force Searching，是两层简单的循环结构。先从 S 第 1 个字符位置开始逐字与 P 字符比较，发现不匹配时，再从 S 第 2 个字符位置开始逐字比较，依次处理直到整个 S 字符串处理完成，算法复杂度是 O(mn)。

输出测试结果：

# 🚩 KMP Search

• - Algorithms 4th - 5.3 Substring Search

• - 有限状态机之 KMP 字符匹配算法 https://labuladong.gitee.io/algo/3/27/99/

• - KMP - Algorithm Visualizer https://algorithm-visualizer.org/dynamic-programming/knuth-morris-pratts-string-search

• - 1143. 最长公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/

• - 14. 最长公共前缀 https://leetcode-cn.com/problems/longest-common-prefix/
  

KMP 字符串查找算法，用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、James H. Morris、Vaughan Pratt 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。

Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

暴力搜索算法中，是两层简单的循环结构。先从 S 第 1 个字符位置开始逐字与 P 字符比较，发现不匹配时，再从 S 第 2 个字符位置开始逐字比较，依次处理直到整个 S 字符串处理完成，算法复杂度是 O(mn)。

如果字符串中重复的字符比较多，或者 P 中有更合适的匹配位置却没有相应处理，该算法就显得很蠢，比如如下数据：

    s = "shellllama" p = "llam"

KMP 算法的不同之处在于，它会花费空间来记录一些信息，这是一处反馈机制，是动态规划算法的特性，在上述情况中就会显得很聪明。

相比暴力的逐字搜索，KMP 算法不用对 S 字符的每一个位置的字符串进行一轮比较，永不回退处理 S 输入字符串。另一个角度来说，KMP 算法回退的是 PMT 查询表的数据。

如果文本串的长度为 n，模式串的长度为 m，那么匹配过程的时间复杂度为 O(n)，整体时间复杂度为 O(m + n)。

而 KMP 算法通过引入一个前缀和后缀的公共字串长度表，也称为部分匹配表 PMT - Partial Match Table，这个表的构建就是 KMP 算法的核心思想：监测到不匹配时，P 提供足够的信息来确定下一次应该从什么位置开始搜索。跳过一些不必要比较的字符串，从而提高了搜索效率，所以把构建出来的这个表称作 next_table 或者 dp_table 都是合适的。

首先了解一些概念：

前缀：以第一个字符开始，但是不包含最后的字符，列如 "abc" 的前缀有 "a" 和 "ab"。

后缀：以最后的字符开始，但是不包含第一个字符，列如 "abc" 的后缀有 "c" 和 "bc"。

最长公共子串：Longest Common Substring 是指两个字符串中最长连续相同的子串长度。 例如 “1AB2345CD” 和 “12345EF” 的最长公共子串为 “2345”，这也是一道算法题目。

子序列：由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

以 Algorithm Visualizer 演示的数据为例：

    S = "AAAABAABAAAABAAABAAAA";

    P = "AAAABAAA";

    S = "Monkey like banana.";

    P = "anana";

首先，KMP 需要根据 P 生成一个 PMT 数据表，以供匹配失败时确定下一个位置，PMT 生成规则，以前缀公共字串长度为例，PMT 每个值是 P 对应位置的匹配前缀字符数量，前缀长度，所以开始位置总是 0：

    PMT: 0 1 2 3 0 1 2 3      | Group

      P: A A A A B A A A      |   A

    PMT: 0 1 0 0              | Group

      P: l l a m              |   B

    PMT: 0 0 1 2              | Group

      P: n a n a              |   C

以上 A、B、C 三组数据产生的 PMT 如何使用呢？还是拿 P 去匹配 S 字符串，从头开始，以 B 组数据为例：

    S: s h e l l l l a m a

       1 2 3 4 5 6 7 8 9 0

从 S 开头检索，直到位置 4 出现第一个匹配字符，继续位置 5 出现第二个匹配字符。注意，每出现匹配表示 PMT 数据获取的位置状态也在变化。

检索第 6 个字符时，出现不匹配，这时 PMT 的数据就起作用了。如果是 Violent Search 算法，肯定是推倒重来，从 S 的第 2 个字符开始检索。但是 KMP 算法因为提前准备好了 PMT 数据，第一次出现不匹配时，知道可以从 PMT 表查询到前面可以匹配的前缀长度，即上一个位置有一个目标前缀长度为 1 的匹配子串。

从而可以直接修改 PMT 状态，或者叫做回退 PMT 数据指针位置，从而避免了在 S 字符串中进行回退操作。通常，输入数据中 S 会比 P 大得多，之也就是 KMP 的算法优点所在：高频前缀字符串的优化搜索算法。

# 🚩 Jitter Search

KMP 主要思想是当出现字符串不匹配时，可以通过 PMT 获释已经匹配的前后缀长度，并利用这些长度信息避免从头再去做匹配，考虑 PMT 查询表的构建，KMP 本质上还是线性搜索算法。

实际上，KMP 算法并不比 C 库函数 strstr() 快多少，因为在缺少重复前缀后缀的情况下，KMP 算法并不占优势。

糟糕的情况是 P 长度 S 相近时，这种算法反而表现更差，花大力气生成的 PMT 数据几乎没什么作用。

考虑到 KMP 算法的不足，这里设计了一种带有二分法思维的搜索算法 Jitter Search：

- 第一步，在 S 串中找出所有 P 第一个字符出现的位置，设为 J 集合；

- 第二步，选择一个整数 jitter，比如 P 串长度的一半；

- 第三步，将 J 集合中所有位置偏移 jitter 处且与 P 串相应位置的值相同的过滤出来；

- 重复，这种操作，直到完整匹配结果。

这种算法的优点是结合了二分法及低频过滤器思维，可以高效处理非频繁重复的字符串搜索。空间上需要占用一个 max(S, p) 的数组空间来存储索引值。

以下为 Python 实现代码，在应用中，可以对首字符高频重复的情况做优化：

输出结构：

# 🚩 Sunday Search

• - 28. [Easy] implement strStr() https://leetcode-cn.com/problems/implement-strstr/

• - 187. [Medium] Repeated DNA Sequences https://leetcode.com/problems/repeated-dna-sequences/
  

1977 年，同时期德克萨斯大学 Robert S. Boyer 教授和 J Strother Moore 教授发明了一种新的字符串匹配算法，简称 BM 算法。该算法从模式串的尾部开始匹配，且最坏情况下的时间复杂度为 O(N)。在实践中，比 KMP 从模式串的开头开始匹配的算法效能高，但是这两种算法都需要对 P 进行预处理，算法实现复杂，大大降低的实用性。

A fast string searching algorithm R. Boyer, J. S. Moore Published 1977 Computer Science Commun.

Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

但 BM 算法也还不是现有字符串查找算法中最快的算法，更快的查找算法是 Sunday 算法，由 Daniel M.Sunday 在 1990 年提出，它的思想跟 BM 算法很相似，只不过 Sunday 算法是从前往后匹配，逻辑如下：

➡ 从头开始匹配，失败时关注的是 S 文本串中按 P 匹配长度的下一位置的字符，记为 M；

➡ 如果该字符不在模式串 P 中，这表示 M 位置之前不可能匹配，则下一轮匹配开始位置在偏移 len(P) 距离后；

➡ 如果该字符出现在模式 P **最右侧位置** Q 中，则将 Q 位置与 M 位置对齐后，再开始新一轮匹配搜索。

从右侧检索 P 中的字符位置这一点很关键，这可以保证对齐 S 序列中的 M 位置时不会错失可能匹配的子串。

例如，以下一组数据：

    S = "aloong"

    P = "loon"

第一轮搜索 l:a 就不匹配，所以直接找到 len(P) 位置的 “n”，确认它在 P 串最右侧的位置，字符索引位置按 0 为起始值：

    S = a l o o n g        >>>   S = a l o o n g

        ^       ^M = 4     >>>         ^     ^M = 4

    P = l o o n            >>>   P =   l o o n 

        ^     ^Q = 3       >>>         ^     ^Q = 3

然后，再按对齐后的序列进入第二轮搜索，如果 M 位置的字符没有出现在 P 序列中，这种情况就是最好处理的，也是最有效率的，直接就只可以跳过一长段不可能匹配的子序列，大大提高的检索效率。同时，与 KMP 等算法相比，还可以不事先建立索引表。

输出结果：

Sunday 算法就像在移动一个匹配窗口，连续匹配时窗口就放大，匹配失败就根据 M 指示的字符来调整新窗口位置。实际上是对 BM 算法的优化，并且它更简单易实现。

Sunday 算法可以先对 P 建立查询表，再对 S 进行搜索。那表时的扫描顺序没有限制，为了提高最坏情况下的算法效率，可以对 P 字符按照其出现的概率从小到大的顺序扫描，这样能尽早地确定失配与否。

Horspool 算法的思想有个创新之处就是模式串是从右向左进行比较的，在不匹配情况处理手法和 Sunday 有类似特征。

# 🚩 Tests for String Search

最后，是以上几种字符串搜索算法的测试用例：