一、问题描述
输入原字符串(String)和子串(Pattern)，找到子串在原字符串中第一次出现的位置，两个字符串分别命名为 $s$ 和 $p$
二、暴力检索
暴力检索(Brute Force)是最简单的匹配方法，首先把 $s$ 和 $p$ 左端对齐，从两个字符串头部开始逐位匹配，匹配失败后将 $p$ 右移一位，从 $p$ 的头部和 $s$ 的对应位置重新匹配。
最坏情况下，假设 $s=“xx….xy”$ ，长度为 $N$ ， $p=“xx…xy”$ ，长度为 $M$ ，每次匹配都需要比较全部 $M$ 个字符，而只有最后一次匹配才能匹配成功，所以时间复杂度是 $O(M\times N)$
三、KMP算法
KMP算法全称是Knuth-Morris-Pratt字符串查找算法，算法的核心思想是利用最大相同前缀后缀长度来减少匹配次数。例如 $ABCAB$ 的前缀有 $A$ 、 $AB$ 、 $ABC$ 、 $ABCA$ 四个，后缀有 $B$ 、 $AB$ 、 $CAB$ 、 $BCAB$ 四个，那么他的最大相同前缀后缀就是 $AB$ ，最大相同前缀后缀长度是2。所以对于字符串 $str[0..n]$ 来说，最大相同前缀后缀长度是 $k$ 就表示 $str[0..k-1]=str[n-k+1..n]$ 但 $str[k]\neq str[n-k]$
先默认已经有了记录子串 $p$ 最大相同前缀后缀长度的数组 $F$ ， $F[k]$ 就是 $p[0..k]$ 的最大相同前缀后缀长度。借用某篇博客里的例子，
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b | |
| p： | a | b | a | a | b | b | a | b | a | a | b |
对于 $p=”abaabbabaab”$ ， $F=[0,0,1,1,2,0,1,2,3,4,5]$
$i$ 表示 $s$ 的下标， $j$ 表示 $p$ 的下标，第一次匹配如下， $s[5]$ 和 $p[5]$ 匹配失败。查询 $F[5-1]$ ，发现 $F[4]=2$ ，说明 $p[0..4]$ 的前两位和最后两位能够匹配上，又因为 $p[0..4]=s[0..4]$ ，下次匹配子串 $p$ 就不必只后移一位，可以直接让 $p[0..1]$ 和 $s[3..4]$ 对齐，因为最大相同前缀后缀长度是2就说明当 $p[0..1]$ 和 $s[3..4]$ 之前的位置对齐时，最多能匹配两位，在第三位之前一定会匹配失败。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b |
| p： | a | b | a | a | b | b | a | b | a | a | b | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
第二次匹配如下，发现 $s[13]$ 和 $p[10]$ 匹配失败，查询得到 $F[9]=4$ ，所以下次直接让 $p[0..3]$ 和 $s[9..12]$ 对齐
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b |
| p： | a | b | a | a | b | b | a | b | a | a | b | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
第三次匹配如下，发现 $s[13]$ 和 $p[4]$ 匹配失败，查询得到 $F[3]=1$ ， 所以下次直接让 $p[0]$ 和 $s[12]$ 对齐
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b |
| p： | a | b | a | a | b | b | a | b | a | a | b | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
第四次匹配如下，发现 $s[13]$ 和 $p[1]$ 匹配失败，查询得到 $F[0]=0$ ， 所以下次只能老老实实把 $p$ 右移一位
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b |
| p： | a | b | a | a | b | b | a | b | a | a | b | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
第五次匹配如下，匹配成功
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | a | b | a | a | b | a | a | b | b | a | b | a | a | a | b | a | a | b | b | a | b | a | a | b |
| p： | a | b | a | a | b | b | a | b | a | a | b | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
还剩一个问题是如何预先求解数组 $F$ ，一种简单的方法是用两个指针 $i$、$j$ 错位遍历子串 $p$ 。初始化 $i=1$ 、 $j=0$ ，指针 $i$ 用于主循环，每当 $p[i]=p[j]$ 时，指针 $j$ 才加一，如果 $p[i]\neq p[j]$ 就把 $j$ 打回原位 $j=0$ ， $i$ 遍历的同时能够确定 $F[i]$ ，时间复杂度为 $O(N)$ ，随便用python写了一下
while i<len(a): |
KMP算法的确能够减少匹配次数，一般认为其时间复杂度是 $O(M+N)$ ，但是极端情况下时间复杂度依然可以是 $O(M\times N)$ ，一种情况是子串的 $F$ 数组都是0时，完全用不到 $F$ ，就退化成了暴力检索，另一种情况是 $p=“aa…aa”$ ，最大相同前缀后缀分别就是 $p[0,i-1]$ 和 $p[1,i]$ ，利用 $F$ 数组就相当于只后移一位。
三、RK算法
RK算法全称Rabin-Karp字符串匹配算法，核心思想是利用字符串的哈希值比较替代逐字符匹配，因为一个足够好的哈希函数能够把不同的字符串映射到不同的哈希值，而把相同的字符串映射到相同的哈希值。对于一个 $N$ 位的字符串 $s$ 和一个 $M$ 位的模式串 $p$ ，依次计算 $s[0..M-1]$ 、 $s[M..2M-1]$ 、… 、 $s[N-M+1..N]$ 的哈希值，并与 $p$ 的哈希值进行比较。
由于哈希函数多少有一定的错误率，为了确保字符串匹配的准确度，当哈希值相同时，需要用传统的逐字符比较的方法进行验证，一般认为时间复杂度是 $O(M+N)$ ，但实际的时间复杂度与选择的哈希函数有很大关系，一个差的哈希函数也可以使时间复杂度趋近 $O(M\times N)$
四、BM算法
BM算法全称Boyer-Moore字符串搜索算法，与其他方法不同的是，BM算法从字符串尾部开始匹配，利用坏字符原则和好后缀原则优化模式串 $p$ 的移动距离。
坏字符原则：当匹配失败时， $s[i]\neq p[j]$ ，称 $s[i]$ 为坏字符。此时检查 $s[i]$ 是否出现在匹配失败位置的左侧，即 $p[0..j-1]$ 中是否存在 $p[k]$ 使得 $p[k]=s[i] (k<j)$ ，如果存在一个或多个，选择其中最右的 $p[k]$ 与当前的 $s[i]$ 对齐，如果不存在，就把 $p[0..j-1]$ 全部移动到匹配失败位置后面，也就是把 $p[0]$ 和 $s[i+1]$ 对齐。
好后缀原则：当匹配失败时， $s[i]\neq p[j]$ ，此时检查模式串 $p$ 是否有后缀匹配成功，即 $p[k..m] (k>j)$ 与 $s$ 的相应位置匹配成功，称这样的后缀为好后缀。如果不存在好后缀，就按照朴素方法把 $p$ 后移一位重新匹配。如果存在好后缀，首先检查最长的好后缀是否出现在匹配失败位置之前，即 $p[h..h+m-k]=p[k..m]$ ，如果出现了最长好后缀，就把 $p[h..h+m-k]$ 与当前的 $p[k..m]$ 对齐，如果没有出现，就按照由长到短的顺序依次检查其他好后缀，如果某个好后缀与 $p$ 的某个前缀相等，就把这对前缀后缀对齐。
匹配失败时，分别按照坏字符原则和好后缀原则计算模式串 $p$ 应该向后移动的距离，取二者的最大值作为实际移动距离。借用Moore教授提供的例子，
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | |||||
| p： | e | x | a | m | p | l | e |
第一次匹配如下，对子串 $p$ 从后往前检查，发现 $s[6]\neq p[6]$ 。根据坏字符原则，由于 $s[6]$ 没有在 $p[0..5]$ 中出现过，所以要把 $p[0..5]$ 全部移到坏字符 $s[6]$ 后面，也就是把 $p[0]$ 和 $s[7]$ 对齐，移动距离是7。根据好后缀原则，由于没有好后缀，只能按照朴素方法把 $p$ 后移一位。相比之下，坏字符原则确定的后移距离更长，所以移动距离是7。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | ||||
| p： | e | x | a | m | p | l | e | |||||||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
第二次匹配如下，从后往前检查，发现 $s[13]\neq p[6]$ 。根据坏字符原则，由于 $s[13]=p[4]$ ，所以要把 $p[4]$ 和 $s[13]$ 对齐，移动距离是2。根据好后缀原则，由于没有好后缀，只能按照朴素方法把 $p$ 后移一位。相比之下，坏字符原则确定的后移距离更长，所以移动距离是2。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | ||||
| p： | e | x | a | m | p | l | e | |||||||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
第三次匹配如下，从后往前检查，发现 $s[11]\neq p[2]$ 。根据坏字符原则，由于 $s[11]$ 没有在 $p[0..1]$ 中出现过，所以要把 $p[0..1]$ 全部移到坏字符 $s[11]$ 后面，也就是把 $p[0]$ 和 $s[12]$ 对齐，移动距离是3。根据好后缀原则，发现匹配到 $“mple”$ 、 $“ple”$ 、 $“le”$ 、 $“e”$ 四个好后缀，首先检查最长的好后缀 $“mple”$ 是否出现在匹配失败位置的左侧，发现不存在，然后依次检查其他好后缀是否匹配到子串 $p$ 的前缀，发现 $“e”$ 能够匹配到 $p$ 的前缀，所以把两个 $“e”$ 对齐，也就是把 $p[0]$ 和 $s[15]$ 对齐，移动距离是6。相比之下，好后缀原则确定的后移距离更长，所以移动距离是6。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | ||||
| p： | e | x | a | m | p | l | e | |||||||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
第四次匹配如下，从后往前检查，发现 $s[21]\neq p[6]$ 。根据坏字符原则， $s[21]=p[4]$ ，所以应该把 $p[4]$ 和 $s[21]$ 对齐，移动距离是2。根据好后缀原则，由于没有好后缀，只能按照朴素方法把 $p$ 后移一位。相比之下，坏字符原则确定的后移距离更长，所以移动距离是2。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | ||||
| p： | e | x | a | m | p | l | e | |||||||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
第五次匹配如下，匹配成功
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | h | e | r | e | i | s | a | s | i | m | p | l | e | e | x | a | m | p | l | e | ||||
| p： | e | x | a | m | p | l | e | |||||||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
BM算法是不稳定的贪心算法，最好情况下时间复杂度 $O(N\div M)$ ，最差情况下时间复杂度为 $O(M\times N)$ 。某篇文章里对BF、KMP、BM三种算法进行了测试对比，结果表明匹配花费的时间 $BM<BF<KMP$ ，可见KMP只是理论上的优化，实际使用时很难遇到较多的相同前缀后缀，对此复杂的优化操作就变得多余，导致算法效率甚至不如暴力检索。
五、Horspool 算法
就是BM算法中的坏字符原则
六、Sunday 算法
Sunday 算法从左到右匹配，但每次匹配失败后查看 $s$ 中参与匹配的最后一个字符的下一个字符，在 $p$ 中查找是否存在该字符，也就是当 $p[M-1]$ 与 $s[k]$ 对齐时，查看 $s[k+1]$ 是否在 $p$ 中出现。如果出现一次或多次，把最右的一个与 $s[k+1]$ 对齐，如果没有出现，就把 $p[0]$ 和 $s[k+2]$ 对齐，相当于整个子串跳过 $s[k+1]$ ，举例说明，
| s： | s | u | b | s | t | r | i | n | g | s | e | a | r | c | h | i | n | g | ||
| p： | s | e | a | r | c | h |
第一次匹配如下，从左到右检查，发现 $s[1]\neq p[1]$ ，此时查看 $p[5]$ 所对应的 $s$ 中的字符的下一个字符，也就是 $s[6]$ 是否出现在 $p$ 中，结果是没有出现，所以直接把 $p[0]$ 和 $s[7]$ 对齐。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | s | u | b | s | t | r | i | n | g | s | e | a | r | c | h | i | n | g | |
| p： | s | e | a | r | c | h | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 |
第二次匹配如下，从左到右检查，发现 $s[7]\neq p[0]$ ，此时查看 $s[13]$ 是否出现在 $p$ 中，结果 $s[13]=p[3]$，所以把 $p[3]$ 和 $s[13]$ 对齐。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | s | u | b | s | t | r | i | n | g | s | e | a | r | c | h | i | n | g | |
| p： | s | e | a | r | c | h | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 |
第三次匹配如下，匹配成功。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| s： | s | u | b | s | t | r | i | n | g | s | e | a | r | c | h | i | n | g | |
| p： | s | e | a | r | c | h | |||||||||||||
| j | 0 | 1 | 2 | 3 | 4 | 5 |
Sunday算法类似于BM算法，是不稳定的贪心算法，时间复杂度也和BM算法一样，最好情况下时间复杂度 $O(N\div M)$ ，最差情况下时间复杂度为 $O(M\times N)$ 。二者的思路都是在匹配失败时从尾部入手，便于找到一个相对较远的位置，把模式串移动到该位置，同时保证移动到左侧的任何位置时都无法匹配成功，从而有效减少了匹配次数。
七、AC自动机
AC自动机全称Aho–Corasick算法，是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法。传统的字符串匹配算法只能同时搜索一个子串 $p$ ，在多模式串匹配任务中只能针对每个子串 $p$ 分别从头到尾扫描一遍母串，效率非常低。AC自动机针使用了Trie树存储所有的子串，树的每个节点表示一个字符，以遍历节点的方式匹配母串，每当匹配失败时，转向当前节点的Fail节点继续匹配，母串也可以从当前位置继续向后匹配而不需要返回头部，如此可以实现只遍历母串一次来匹配所有的子串。以下例子转自别人的转自，
假设子串集合为 $p={she,he,say,her,shr}$ ，母串是 $yasherhs$ 。首先根据子串的集合构造Trie树(过程简单直接略过)，结果如下。
注意需要为节点添加一个指针属性，在Trie树构建完毕后，将每个节点的该指针指向他的Fail节点，设置好Fail节点的Trie树如下。假设节点 $i$ 的Fail节点是节点 $j$ ，从根节点到节点 $i$ 的字符串记为 $word[i]$ ，从根节点到节点 $j$ 的字符串记为 $word[j]$ ，那么Fail节点的含义就是 $word[j]$ 是 $word[i]$ 在树中以根节点为起点的最长后缀。例如图中右侧 $she$ 的 $e$ 节点的Fail节点是左侧 $he$ 的 $e$ 节点，表示 $he$ 是 $she$ 在树中的最长后缀。
Fail节点的设置只需要遵循一个原则，一个节点 $i$ 的Fail指针指向他父节点的Fail节点的与 $i$ 同名的子节点。这里涉及了四个节点，举例来说，为图中最右的 $h$ 节点指定Fail节点，他的父节点是 $s$ ， $s$ 的Fail指针指向根节点，根节点的孩子中存在与 $h$ 同名的节点，也就是最左的 $h$ 节点，所以最右的 $h$ 节点的Fail指针应该指向最左的 $h$ 节点。如果不存在这样的节点，就把Fail指针指向根节点，比如图中两个 $r$ 节点。此外，根节点不需要设置Fail指针。在这个过程中，回溯父节点的步骤可以通过递归实现，遍历到子节点的同时把父节点的Fail指针传递给子节点。
母串 $yasherhs$ 的匹配过程：
第一步，当前节点是根节点，查找字符是 $y$ ，发现根节点没有为 $y$ 的子节点，又因为根节点没有Fail节点，所以留在原地，母串索引加一。
第二步，当前节点是根节点，查找字符是 $a$ ，发现根节点没有为 $a$ 的子节点，又因为根节点没有Fail节点，所以留在原地，母串索引加一。
第三步，当前节点是根节点，查找字符是 $s$ ，因此转到根节点的右子节点 $s$ ，匹配成功，母串索引加一。
第四步，当前节点是 $s$ ，查找字符是 $h$ ，因此转到根节点的右子节点 $h$ ，匹配成功，母串索引加一。
第五步，当前节点是 $h$ ，查找字符是 $e$ ，因此转到根节点的左子节点 $e$ ，该节点同时是词尾节点，说明子串 $she$ 匹配成功，母串索引加一。
第六步，当前节点是 $e$ ，查找字符是 $r$ ，因为当前节点没有子节点，匹配失败，转向他的Fail节点，也就是左侧的 $e$ 节点，发现该节点是词尾节点，说明子串 $he$ 匹配成功，同时该节点的子节点包含目标字符 $r$ ，因此转向左子节点 $r$ ，发现节点 $r$ 也是词尾节点，说明子串 $her$ 匹配成功。母串索引加一。
第七步，当前节点是 $r$ ，查找字符是 $h$ ，因为当前节点没有子节点，匹配失败，转向他的Fail节点，也就是根节点，根节点的子节点包含目标字符 $h$ ，因此转向左侧的节点 $h$ ，母串索引加一。
第八步，当前节点是 $h$ ，查找字符是 $s$ ，因为当前节点的子节点没有 $s$ ，匹配失败，转向他的Fail节点，也就是根节点，根节点的子节点包含目标字符 $s$ ，因此转向右侧的节点 $s$ ，母串索引到头了，匹配结束。
整个匹配过程中，母串仅遍历了一次，匹配了多个子串，大大提高了匹配效率。Fail指针的合理性在于指向以根节点为起点的最长后缀，一方面，以根节点为起始说明这个后缀同时也是某个子串的前缀，从Fail节点开始匹配就相当于在默认匹配了某个子串前缀的条件下，从该子串的中间继续匹配。另一方面，指向最长后缀能够保证不会漏掉能够匹配到子串的有效后缀，假如一个节点有两个有效后缀，一定是该节点的Fail指针指向最长后缀，最长后缀的Fail指针指向次长后缀。
