字符串匹配 | 彩潭有鲤的札记

type

status

date

slug

summary

Brute Force 算法

Brute Force 算法：简称为 BF 算法，暴力匹配算法，也可以叫做朴素匹配算法。

BF 算法思想：对于给定文本串 T 与模式串 p，从文本串的第一个字符开始与模式串 p 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 T 的第二个字符起重新和模式串 p 进行比较。依次类推，直到模式串 p 中每个字符依次与文本串 T 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。

BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行m次字符对比，总共需要进行n-m+1轮比较，总的比较次数为m*(n-m+1) 。所以BF算法的最坏时间复杂度为

在最理想的情况下（第一次匹配直接匹配成功），BF 算法的最佳时间复杂度是

在一般情况下，根据等概率原则，平均搜索次数为，所以 Brute Force 算法的平均时间复杂度为

Rabin Karp

Rabin Karp 算法：简称为RK算法。是由它的两位发明者 Michael Oser Rabin 和 Richard Manning Karp 的名字来命名的。RK 算法是他们在 1987 年提出的、使用哈希函数以在文本中搜寻单个模式串的字符串搜索算法。

Rabin Karp 算法思想：对于给定文本串T与模式串p，通过滚动哈希算快速筛选出与模式串p不匹配的文本位置，然后在其余位置继续检查匹配项。

Rabin Karp 算法整体步骤

对于给定的文本串T与模式串p，求出文本串T的长度为n，模式串p的长度为m

通过滚动哈希算法求出模式串p的哈希值hash_p

再通过滚动哈希算法对文本串T中n - m + 1 个子串分别求哈希值 hash_t

然后逐个与模式串的哈希值比较大小。

如果当前子串的哈希值hash_t与模式串的哈希值hash_p不同，则说明两者不匹配，则继续向后匹配
如果当前子串的哈希值hash_t与模式串的哈希值hash_p相等，则验证当前子串和模式串的每个字符是否真的相等（避免哈希冲突）

如果当前子串和模式串的每个字符相等，则说明当前子串和模式串匹配

如果当前子串和模式串的每个字符不相等，则说明两者不匹配，继续向后匹配

比较到末尾，如果仍未成功匹配，则说明文本串T中不包含模式串p，方法返回1。

滚动哈希算法

实现 RK 算法中一个重要步骤是 「滚动哈希算法」，通过滚动哈希算法，将每次计算子串哈希值的复杂度从降到了，从而提升了整个算法效率。

RK 算法中的滚动哈希算法主要是利用了 「Rabin fingerprint 思想」。这种算法思想利用了子串中每一位字符的哈希值，并且还可以根据上一个子串的哈希值，快速计算相邻子串的哈希值，从而使得每次计算子串哈希值的时间复杂度降为了。

假设给定的字符串的字符集中只包含 d 种字符，那么就可以用一个 d 进制数表示子串的哈希值。假如字符串只包含 a ~ z 这 26 个小写字母，那么就可以用26进制数来表示一个字符串，a表示为0，b表示为1，以此类推，z就用25表示。

比如cat的哈希值就可以表示为：

这种按位计算哈希值的哈希函数有一个特点：在计算相邻子串时，可以利用上一个子串的哈希值。

比如说 cat 的相邻子串为 ate。按照刚才哈希函数计算，可以得出 ate 的哈希值为：

如果利用上一个子串 cat 的哈希值计算 ate，则 ate 的哈希值为：

可以看出，这两种方式计算出的哈希值是相同的。但是第二种计算方式不需要再遍历子串，只需要进行一位字符的计算即可得出整个子串的哈希值。这样每次计算子串哈希值的时间复杂度就降到了。然后就可以通过滚动哈希算法快速计算出子串的哈希值了。

给定的文本串T与模式串p，求出文本串T的长度为n，模式串p的长度为m。字符串字符种类数为d，则：

模式串p的哈希值计算方式为：

文本串中起始于位置0，长度为m的子串对应哈希值计算方法为：

已知子串的哈希值，将子串向右移动一位的子串对应哈希值计算方法为：

因为哈希值过大会造成溢出，所以在计算过程中还要对结果取模。取模的值应该尽可能大，并且应该是质数，这样才能减少哈希碰撞的概率。

RK 算法可以看做是 BF 算法的一种改进。在 BF 算法中，每一个字符都需要进行比较。而在 RK 算法中，判断模式串的哈希值与每个子串的哈希值之间是否相等的时间复杂度为。总共需要比较 n-m+1 个子串的哈希值，所以 RK 算法的整体时间复杂度为。跟 BF 算法相比，RK 算法的效率提高了很多。

但是如果存在冲突的情况下，算法的效率会降低。最坏情况是每一次比较模式串的哈希值和子串的哈希值时都相等，但是每一次都会出现冲突，那么每一次都需要验证模式串和子串每个字符是否完全相同，那么总的比较次数就是m*(n-m+1) ，时间复杂度就会退化为。

KMP

KMP 算法：全称叫做 「Knuth Morris Pratt 算法」，是由它的三位发明者 Donald Knuth、James H. Morris、 Vaughan Pratt 的名字来命名的。KMP 算法是他们三人在 1977 年联合发表的。

KMP 算法思想：对于给定文本串 T 与模式串 p，当发现文本串 T 的某个字符与模式串 p 不匹配的时候，可以利用匹配失败后的信息，尽量减少模式串与文本串的匹配次数，避免文本串位置的回退，以达到快速匹配的目的。

朴素匹配算法的缺陷

在朴素匹配算法的匹配过程中，分别用指针i和指针j指示文本串T和模式串p中当前正在对比的字符。当发现文本串T的某个字符与模式串p不匹配的时候，j回退到开始位置，i回退到之前匹配开始位置的下一个位置上，然后开启新一轮的匹配。

这样，在 Brute Force 算法中，如果从文本串 T[i] 开始的这一趟字符串比较失败了，算法会直接开始尝试从 T[i + 1] 开始比较。如果 i 已经比较到了后边位置，则该操作相当于将指针i进行了回退操作。

那么有没有哪种算法，可以让 i 不发生回退，一直向右移动呢？

KMP 算法的改进

如果可以通过每一次的失配而得到一些「信息」，并且这些「信息」可以帮助我们跳过那些不可能匹配成功的位置，那么就能大大减少模式串与文本串的匹配次数，从而达到快速匹配的目的。

每一次失配所告诉我们的信息是：主串的某一个子串等于模式串的某一个前缀。

这个信息的意思是：如果文本串 T[i: i + m] 与模式串p的失配是下标位置 j 上发生的，那么文本串T从下标位置i开始连续的j - 1个字符，一定与模式串p的前j - 1 个字符一模一样，即：T[i:i + j] == p[0:j]。

但是知道这个信息有什么用呢？

以刚才图中的例子来说，文本串的子串 T[i:i+m] 与模式串 p 的失配是在第 5 个位置发生的，那么：

文本串 T 从下标位置 i 开始连续的 5 个字符，一定与模式串 p 的前 5 个字符一模一样，即："ABCAB" == "ABCAB"。

而模式串的前 5 个字符中，前 2 位前缀和后2位后缀又是相同的，即"AB" == "AB"。

所以根据上面的信息，可以推出：文本串子串的后2位后缀和模式串子串的前2位是相同的，即T[i+3: i+5] == p[0:2]，而这部分（即下图中的蓝色部分）是之前已经比较过的，不需要再比较了，可以直接跳过。

那么就可以将文本串中的 T[i+5] 对准模式串中的p[2]，继续进行对比。这样i就不再需要回退了，可以一直向右移动匹配下去。在这个过程中，只需要将模式串 j 进行回退操作即可。

KMP 算法就是使用了这样的思路，对模式串p 进行了预处理，计算出一个 「部分匹配表」，用一个数组next 来记录。然后在每次失配发生时，不回退文本串的指针i，而是根据「部分匹配表」中模式串失配位置j 的前一个位置的值，即next[j-1] 的值来决定模式串可以向右移动的位数。

比如上述示例中模式串p是在j = 5的位置上发生失配的，则说明文本串的子串 T[i:i+5] 和模式串p[0:5] 的字符是一致的，即"ABCAB" == "ABCAB"。而根据「部分匹配表」中 next[4]==2，所以不用回退i，而是将j移动到下标为2的位置，让T[i+5]直接对准p[2]，然后继续进行比对。

失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值

next 数组

「部分匹配表」，也叫做「前缀表」，在 KMP 算法中使用 next 数组存储。next[j] 表示的含义是：记录下标 j 之前（包括 j）的模式串 p 中，最长相等前后缀的长度。

简单而言，就是求：模式串 p 的子串 p[0:j + 1] 中，使得「前 k 个字符」恰好等于「后 k 个字符」的「最长的 k」。当然子串 p[0: j + 1] 本身不参与比较。

前缀：包括首元素不包括尾元素的所有字串，都称为前缀

后缀：包括尾元素不包括首元素的所有字串，都称为后缀

以 p = "ABCABCD" 为例：

next[0] = 0，因为 "A" 中无有相同前缀后缀，最大长度为 0。

next[1] = 0，因为 "AB" 中无相同前缀后缀，最大长度为 0。

next[2] = 0，因为 "ABC" 中无相同前缀后缀，最大长度为 0。

next[3] = 1，因为 "ABCA" 中有相同的前缀后缀 "a"，最大长度为 1。

next[4] = 2，因为 "ABCAB" 中有相同的前缀后缀 "AB"，最大长度为 2。

next[5] = 3，因为 "ABCABC" 中有相同的前缀后缀 "ABC"，最大长度为 3。

next[6] = 0，因为 "ABCABCD" 中无相同前缀后缀，最大长度为 0。

同理， "ABCABDEF"的前缀表为[0,0,0,1,2,0,0,0]。"AABAAAB"的前缀表为[0,1,0,1,2,2,3]。"ABCDABD"的前缀表为 [0,0,0,0,1,2,0]。

在之前的例子中，当p[5]和T[i+5]匹配失败后，根据模式串失配位置j的前一个位置的值，即next[4] = 2，直接让T[i+5]直接对准了p[2]，然后继续进行比对:

但是这样移动的原理是什么？

这个过程就是利用了前缀表进行模式串移动的原理，如果文本串 T[i:i+m]与模式串p的失配是在第j个下标位置发生的，那么：

文本串T从下标位置i开始连续的j个字符，一定与模式串p的前j个字符一模一样，即：T[i:i+j] == p[0:j]

而如果模式串p的前j个字符中，前k位前缀和后k位后缀相同，即p[0:k] == p[j-k:j]，并且要保证k要尽可能长

可以推出：文本串子串的后k位后缀和模式串子串的前k位是相同的，即T[i+m-k: i+m] == p[0:k]（这部分是已经比较过的），不需要再比较了，可以直接跳过。

那么就可以将文本串中的 T[i+m]对准模式串中的p[k]，继续进行对比。这里的k其实就是next[j-1]。

next 数组的构造

可以通过递推的方式构造 next 数组。

把模式串p拆分成left、right两部分。left表示前缀串开始所在的下标位置，right表示后缀串开始所在的下标位置，起始时left = 0，right = 1

比较一下前缀串和后缀串是否相等。通过比较p[left]和p[right]来进行判断。

如果p[left] != p[right]，说明当前的前后缀不相同。则让后缀开始位置k不动，前缀串开始位置left不断回退到next[left-1]位置，直到p[left] == p[right]为止。

如果 p[left] == p[right]，说明当前的前后缀相同，则可以先让left += 1，此时left既是前缀下一次进行比较的下标位置，又是当前最长前后缀的长度。

记录下标right之前的模式串p中，最长相等前后缀的长度为 left，即next[right] = left。

KMP算法匹配过程示例

当空格与D不匹配时，知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6-2 等于4，所以将搜索词向后移动4位：

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位：

因为空格与A不匹配，继续后移一位：

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位：

KMP 算法整体步骤

根据 next 数组的构造步骤生成「前缀表」next。

使用两个指针 i、j，其中 i 指向文本串中当前匹配的位置，j 指向模式串中当前匹配的位置。初始时，i = 0，j = 0。

循环判断模式串前缀是否匹配成功，如果模式串前缀匹配不成功，将模式串进行回退，即 j = next[j - 1]，直到 j == 0 时或前缀匹配成功时停止回退。

如果当前模式串前缀匹配成功，则令模式串向右移动 1 位，即 j += 1。

如果当前模式串完全匹配成功，则返回模式串 p 在文本串 T 中的开始位置，即 i - j + 1。

如果还未完全匹配成功，则令文本串向右移动 1 位，即 i += 1，然后继续匹配。

如果直到文本串遍历完也未完全匹配成功，则说明匹配失败，返回 -1。

复杂度分析

KMP 算法在构造前缀表阶段的时间复杂度为，其中是模式串p的长度。

KMP 算法在匹配阶段，是根据前缀表不断调整匹配的位置，文本串的下标i 并没有进行回退，可以看出匹配阶段的时间复杂度是，其中是文本串T的长度。

所以 KMP 整个算法的时间复杂度是，相对于朴素匹配算法的的时间复杂度，KMP算法的效率有了很大的提升。

Boyer Moore

Boyer Moore 算法：简称为 BM 算法，是由它的两位发明者 Robert S. Boyer 和 J Strother Moore 的名字来命名的。BM 算法是他们在 1977 年提出的高效字符串搜索算法。在实际应用中，比 KMP 算法要快 3~5 倍。

BM 算法思想：对于给定文本串T与模式串p，先对模式串p进行预处理。然后在匹配的过程中，当发现文本串T的某个字符与模式串p不匹配的时候，根据启发策略，能够直接尽可能地跳过一些无法匹配的情况，将模式串多向后滑动几位。

BM 算法的精髓在于使用了两种不同的启发策略来计算后移位数：「坏字符规则（The Bad Character Rule）」 和 「好后缀规则（The Good Suffix Shift Rule）」。

这两种启发策略的计算过程只与模式串p相关，而与文本串T无关。因此在对模式串p进行预处理时，可以预先生成「坏字符规则后移表」和「好后缀规则后移表」，然后在匹配的过程中，只需要比较一下两种策略下最大的后移位数进行后移即可。

还需要注意一点：BM 算法在移动模式串的时候和常规匹配算法一样是从左到右进行，但是在进行比较的时候是从右到左，即基于后缀进行比较。

坏字符规则（The Bad Character Rule）

当文本串T中某个字符跟模式串p的某个字符不匹配时，则称文本串T中这个失配字符为 「坏字符」，此时模式串p可以快速向右移动。坏字符规则的移动位数分为两种情况：

情况 1：坏字符出现在模式串 p 中

这种情况下，可将模式串中最后一次出现的坏字符与文本串中的坏字符对齐，向右移动位数 = 坏字符在模式串中的失配位置 - 坏字符在模式串中最后一次出现的位置

情况 2：坏字符没有出现在模式串 p 中

这种情况下，可将模式串向右移动一位，向右移动位数 = 坏字符在模式串中的失配位置 + 1

好后缀规则（The Good Suffix Shift Rule）

当文本串T中某个字符跟模式串p的某个字符不匹配时，则称文本串T中已经匹配好的字符串为 「好后缀」，此时模式串 p 可以快速向右移动。好后缀规则的移动方式分为三种情况：

情况 1：模式串中有子串匹配上好后缀

这种情况下，移动模式串，让该子串和好后缀对齐即可。如果超过一个子串匹配上好后缀，则选择最右侧的子串对齐，向右移动位数 = 好后缀的最后一个字符在模式串中的位置 - 匹配的子串最后一个字符出现的位置。

情况 2：模式串中无子串匹配上好后缀，但有最长前缀匹配好后缀的后缀

这种情况下，需要在模式串的前缀中寻找一个最长前缀，该前缀等于好后缀的后缀。找到该前缀后，让该前缀和好后缀的后缀对齐。向右移动位数 = 好后缀的后缀的最后一个字符在模式串中的位置 - 最长前缀的最后一个字符出现的位置。

情况 3：模式串中无子串匹配上好后缀，也找不到前缀匹配

可将模式串整个右移，向右移动位数 = 模式串的长度。

Boyer Moore 算法匹配过程示例

假设文本串为 "HERE IS A SIMPLE EXAMPLE"，模式串为 "EXAMPLE"：

首先，令模式串与文本串的头部对齐，然后从模式串的尾部开始逐位比较：

可以看出来，'S' 与 'E' 不匹配。这时候，不匹配的字符 'S' 就被称为「坏字符（Bad Character）」，对应着模式串的第 6 位。并且 'S' 并不包含在模式串 "EXAMPLE" 中（相当于'S' 在模式串中最后一次出现的位置是 -1）。根据「坏字符规则」，可以把模式串直接向右移动 6 - (-1) = 7 位，即将文本串中 'S' 的后一位上。

将模式串向右移动 7 位。然后依然从模式串尾部开始比较，发现 'P' 和 'E' 不匹配，则 'P' 是坏字符：

但是 'P' 包含在模式串 "EXAMPLE" 中，'P' 这个坏字符在模式串中的失配位置是第 6 位，并且在模式串中最后一次出现的位置是 4（编号从 0 开始）。

根据「坏字符规则」，可以将模式串直接向右移动 6-4 = 2 位，将文本串的 'P' 和模式串中的 'P' 对齐：

继续从尾部开始逐位比较。先比较文本串的 'E' 和模式串的 'E'，如下图所示。可以看出文本串的 'E' 和模式串的 'E' 匹配，则 "E" 为好后缀，"E" 在模式串中的位置为 6（编号从 0 开始）。

继续比较前面一位，即文本串的 'L' 和模式串的 'L'，如下图所示。可以看出文本串的 'L' 和模式串的 'L' 匹配。则 "LE" 为好后缀，"LE" 在模式串中的位置为 6（编号从 0 开始）。

继续比较前面一位，即文本串中的 'P' 和模式串中的 'P'，如下图所示。可以看出文本串中的 'P' 和模式串中的 'P' 匹配，则 "PLE" 为好后缀，"PLE" 在模式串中的位置为 6（编号从 0 开始）。

继续比较前面一位，即文本串中的 'M' 和模式串中的 'M'，如下图所示。可以看出文本串中的 'M' 和模式串中的 'M' 匹配，则 "MPLE" 为好后缀。"MPLE" 在模式串中的位置为 6（编号从 0 开始）。

继续比较前面一位，即文本串中的 'I' 和模式串中的 'A'，如下图所示。可以看出文本串中的 'I' 和模式串中的 'A' 不匹配。

此时，如果按照「坏字符规则」，模式串应该向右移动 2 - (-1) = 3 位。但是根据「好后缀规则」，我们还有更好的移动方法。

在好后缀 "MPLE" 和好后缀的后缀 "PLE"、"LE"、"E" 中，只有好后缀的后缀 "E" 和模式串中的前缀 "E" 相匹配，符合好规则的第二种情况。好后缀的后缀 "E" 的最后一个字符在模式串中的位置为 6，最长前缀 "E"的最后一个字符出现的位置为 0，则根据「好后缀规则」，可以将模式串直接向右移动 6 - 0 = 6 位。如下图所示。

继续从模式串的尾部开始逐位比较，如下图所示。

可以看出，'P' 与'E' 不匹配，'P' 是坏字符。根据「坏字符规则」，可以将模式串直接向右移动 6 - 4 = 2 位

继续从模式串的尾部开始逐位比较，发现模式串全部匹配，于是搜索结束，返回模式串在文本串中的位置。

Boyer Moore 算法步骤

整个 BM 算法步骤描述如下：

计算出文本串T的长度为n，模式串p的长度为m。

先对模式串p进行预处理，生成坏字符位置表bc_table和好后缀规则后移位数表gs_talbe。

将模式串p的头部与文本串T对齐，将i指向文本串开始位置，即i = 0。j指向模式串末尾位置，即j = m-1，然后从模式串末尾位置开始进行逐位比较。

如果文本串对应位置 T[i+j] 上的字符与 p[j] 相同，则继续比较前一位字符。

如果模式串全部匹配完毕，则返回模式串 p 在文本串中的开始位置 i。

如果文本串对应位置 T[i+j] 上的字符与 p[j] 不相同，则：

根据坏字符位置表计算出在「坏字符规则」下的移动距离 bad_move。
根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离 good_mode。
取两种移动距离的最大值，然后对模式串进行移动，即 i += max(bad_move, good_move)。

如果移动到末尾也没有找到匹配情况，则返回 -1。

生成坏字符位置表

生成坏字符位置表的具体步骤如下：

使用一个哈希表 bc_table， bc_table[bad_char] 表示坏字符 bad_char 在模式串中出现的最右位置。

遍历模式串，以当前字符p[i]为键，所在位置下标为值存入字典中。如果出现重复字符，则新的位置下标值会将之前存放的值覆盖掉。这样哈希表中存放的就是该字符在模式串中出现的最右侧位置。

这样如果在BM算法的匹配过程中，如果bad_char不在bc_table中时，可令bad_char在模式串中出现的最右侧位置为-1。如果bad_char在bc_table中时，bad_char在模式串中出现的最右侧位置就是 bc_table[bad_char]。这样就可以根据公式计算出可以向右移动的位数了。

生成好后缀规则后移位数表

为了生成好后缀规则后移位数表，需要先定义一个后缀数组suffix，其中suffix[i] = s 表示为以下标i为结尾的子串与模式串后缀匹配的最大长度为s。即满足p[i-s...i] == p[m-1-s, m-1] 的最大长度为s。

构建 suffix 数组的代码如下：

有了 suffix 数组，就可以在此基础上定义好后缀规则后移位数表 gs_list。使用一个数组来表示好后缀规则后移位数表。其中gs_list[j]表示在 j 下标处遇到坏字符时，可根据好规则向右移动的距离。

由好后缀规则中可知，好后缀规则的移动方式可以分为三种情况。

情况 1：模式串中有子串匹配上好后缀。

情况 2：模式串中无子串匹配上好后缀，但有最长前缀匹配好后缀的后缀。

情况 3：模式串中无子串匹配上好后缀，也找不到前缀匹配。

这 3 种情况中，情况 2 和情况 3 可以合并，因为情况 3 可以看做是匹配到的最长前缀长度为 0。而如果遇到一个坏字符同时满足多种情况，则应该选择满足情况中最小的移动距离才不会漏掉可能匹配的情况，比如说当模式串中既有子串可以匹配上好后缀，又有前缀可以匹配上好后缀的后缀，则应该按照前者的方式移动模式串。

为了得到精确的 gs_list[j]，我们可以先假定所有情况都为情况 3，即 gs_list[i] = m。

然后通过后缀和前缀匹配的方法，更新情况 2 下gs_list中坏字符位置处的值，即gs_list[j] = m-1-i，其中j是好后缀前的坏字符位置，i是最长前缀的末尾位置，m - 1 - i 是可向右移动的距离。

最后再计算情况 1 下 gs_list 中坏字符位置处的值，更新在好后缀的左端点处（m - 1 - suffix[i] 处）遇到坏字符可向后移动位数，即 gs_list[m - 1 - suffix[i]] = m - 1 - i。

生成好后缀规则后移位数表 gs_list 代码如下：

Boyer Moore 算法代码实现

BM 算法在预处理阶段的时间复杂度为，其中 σ 是字符集的大小。

BM 算法在搜索阶段最好情况是每次匹配时，模式串 p 中不存在与文本串 T 中第一个匹配的字符。这时的时间复杂度为 O(n/m)。

BM 算法在搜索阶段最差情况是文本串 T 中有多个重复的字符，并且模式串 p 中有 m - 1 个相同字符前加一个不同的字符组成。这时的时间复杂度为。

当模式串 p 是非周期性的，在最坏情况下，BM 算法最多需要进行 3∗n 次字符比较操作。

Horspool

Horspool 算法：是一种在字符串中查找子串的算法，它是由 Nigel Horspool 教授于 1980 年出版的，是首个对 Boyer Moore 算法进行简化的算法。

Horspool 算法思想：对于给定文本串T与模式串p，先对模式串p进行预处理。然后在匹配的过程中，当发现文本串T的某个字符与模式串p不匹配的时候，根据启发策略，能够尽可能的跳过一些无法匹配的情况，将模式串多向后滑动几位。

可以看出，Horspool 算法思想和 Boyer Moore 算法思想是一致的。Horspool 算法是在 Boyer Moore 算法思想基础上改进了「坏字符规则」。当文本串T中某个字符跟模式串 p的某个字符不匹配时，可以模式串p快速向右移动。

遇到不匹配字符时，可以根据以下两种情况向右快速进行移动：

情况 1：文本串T中与模式串p尾部字符p[m-1]对应的字符T[i+m-1]出现在模式串p中。

这种情况下，可将 T[i+m-1] 与模式串中最后一次出现的该字符对齐，向右移动位数 = 模式串最后一个字符的位置 - T[i + m - 1] 在模式串中最后一次出现的位置。注意：模式串最后一个字符的位置其实就是「模式串长度 - 1」。

情况 2：文本串T中与模式串p尾部字符 p[m-1]对应的字符T[i+m-1] 没有出现在模式串p中

这种情况下，可将模式串整个右移，向右移动位数 = 整个模式串长度。

整个 Horspool 算法步骤描述如下：

计算出文本串 T 的长度为 n，模式串 p 的长度为 m

先对模式串 p 进行预处理，生成后移位数表 bc_table。

将模式串 p 的头部与文本串 T 对齐，将 i 指向文本串开始位置，即 i = 0。j 指向模式串末尾位置，即 j = m - 1，然后从模式串末尾位置开始比较。

如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 相同，则继续比较前一位字符。

如果模式串全部匹配完毕，则返回模式串 p 在文本串中的开始位置 i。

如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 不同，则：

根据后移位数表 bc_table 和模式串末尾位置对应的文本串上的字符 T[i + m - 1] ，计算出可移动距离 bc_table[T[i + m - 1]]，然后将模式串进行后移。

如果移动到末尾也没有找到匹配情况，则返回 1。

后移位数表

跟Boyer Moore算法中生成坏字符位置表的差不多：

使用一个哈希表bc_table，bc_table[bad_char]表示表示遇到坏字符可以向右移动的距离

遍历模式串，以当前字符p[i]为键，可以向右移动的距离（m - 1 - i）为值存入字典中。如果出现重复字符，则新的位置下标值会将之前存放的值覆盖掉。这样哈希表中存放的就是该字符在模式串中出现最右侧位置上的可向右移动的距离。

如果在 Horspool 算法的匹配过程中，如果 T[i+m-1]不在bc_table中时，可令其为m，表示可以将模式串整个右移。如果T[i+m-1]在bc_table中时，可移动距离就是bc_table[T[i+m-1]] 。这样就能计算出可以向右移动的位数了。

生成后移位数表的代码如下：

和BM不一样的是，这个坏字符表的数值和BM是相反的，BM是递增，Horspool是递减。相同之处则是，如果遇到相同字符，以最右侧的字符的值为准。

这次的实现则只有坏字符表，因为这里的坏字符采用的是逐渐递减的移位方式，如果匹配失败，则对比后缀最后一位数字，来进行移位操作。

Horspool算法在平均情况下的时间复杂度为，但是在最坏情况下时间复杂度会退化为。

Sunday

Sunday 算法是一种在字符串中查找子串的算法，是 Daniel M.Sunday 于1990年提出的字符串模式匹配算法。

Sunday 算法思想：对于给定文本串 T 与模式串 p，先对模式串 p 进行预处理。然后在匹配的过程中，当发现文本串 T 的某个字符与模式串 p 不匹配的时候，根据启发策略，能够尽可能的跳过一些无法匹配的情况，将模式串多向后滑动几位。

Sunday 算法思想跟 Boyer Moore 算法思想类似。不同的是，Sunday 算法匹配顺序是从左向右，并且在模式串 p 匹配失败时关注的是文本串 T 中参加匹配的末尾字符的下一位字符。当文本串 T 中某个字符跟模式串 p 的某个字符不匹配时，可以将模式串 p 快速向右移动。

遇到不匹配字符时，可以根据以下两种情况向右快速进行移动：

情况 1：文本串 T 中与模式串 p 尾部字符 p[m - 1] 对应的字符下一个位置的字符 T[i + m] 出现在模式串 p 中

这种情况下，可将T[i + m] 与模式串中最后一次出现的该字符对齐，向右移动位数 = 文本串 T 中与模式串 p 尾部位置的下一个位置 - T[i + m] 在模式串中最后一次出现的位置。

注意：文本串 T 中与模式串 p 尾部位置的下一个位置其实就是「模式串长度」。

情况 2：文本串 T 中与模式串 p 尾部字符 p[m - 1] 对应的字符下一个位置的字符 T[i + m] 没有出现在模式串 p 中

这种情况下，可将模式串整个右移，向右移动位数 = 整个模式串长度 + 1。

整个 Sunday 算法步骤描述如下：

计算出文本串 T 的长度为 n，模式串 p 的长度为 m。

先对模式串 p 进行预处理，生成后移位数表 bc_table。

将模式串 p 的头部与文本串 T 对齐，将 i 指向文本串开始位置，即 i = 0。j 指向模式串开始，即 j = 0，然后从模式串开始位置开始比较。

如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 相同，则继续比较后一位字符。

如果模式串全部匹配完毕，则返回模式串 p 在文本串中的开始位置 i。

如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 不同，则：

根据后移位数表 bc_table 和模式串末尾位置对应的文本串上的字符 T[i + m] ，计算出可移动距离 bc_table[T[i + m]]，然后将模式串进行后移。

如果移动到末尾也没有找到匹配情况，则返回 -1。

后移位数表

生成后移位数表的代码实现比较简单，跟 Horspool 算法中生成后移位数表的代码差不多。具体步骤如下：

使用一个哈希表 bc_table， bc_table[bad_char] 表示表示遇到坏字符可以向右移动的距离。

遍历模式串，以当前字符 p[i] 为键，可以向右移动的距离（m - i）为值存入字典中。如果出现重复字符，则新的位置下标值会将之前存放的值覆盖掉。这样哈希表中存放的就是该字符在模式串中出现最右侧位置上的可向右移动的距离。

如果在 Sunday 算法的匹配过程中，如果 T[i + m] 不在 bc_table 中时，可令其为 m + 1，表示可以将模式串整个右移到上一次匹配末尾后边两个位置上。如果 T[i + m] 在 bc_table 中时，可移动距离就是 bc_table[T[i + m]] 。这样就能计算出可以向右移动的位数了。

Sunday算法代码实现

Sunday算法在平均情况下的时间复杂度为，但是在最坏情况下时间复杂度会退化为