字符串匹配算法的实现细则

字符串匹配算法的实现细则一、概述

字符串匹配算法是计算机科学中的一项基础技术，广泛应用于文本处理、数据检索、信息安全等领域。其核心任务是在一个较长的文本串（主串）中查找是否存在一个较短的子串（模式串），并返回子串在主串中的起始位置。根据不同的应用场景和性能要求，存在多种字符串匹配算法，如暴力匹配、KMP算法、Boyer-Moore算法等。本文档将详细介绍几种典型字符串匹配算法的实现细节，包括其原理、步骤及优缺点分析。

---

二、暴力匹配算法

暴力匹配算法是最基础的字符串匹配方法，其基本思想是逐个比较模式串与主串中每个可能的子串，直到找到匹配或遍历完主串。

（一）算法原理

暴力匹配的核心是通过双层循环实现：外层循环遍历主串的每个字符，内层循环逐个比较模式串与主串的子串。若所有字符匹配成功，则返回匹配位置；若遇到不匹配，则内层循环终止，外层循环移动到下一个位置继续比较。

（二）实现步骤

1.初始化：设置主串指针`i`从0开始，模式串指针`j`也从0开始。

2.外层循环：遍历主串，`i`从0到`n-m`（`n`为主串长度，`m`为模式串长度）。

3.内层循环：逐个比较主串`text[i..i+m-1]`与模式串`pattern[0..m-1]`。

-若字符匹配（`text[i+j]==pattern[j]`），则`j`加1。

-若`j`等于模式串长度，说明匹配成功，返回`i`。

-若字符不匹配，重置`j`为0，`i`加1。

4.匹配失败：若外层循环结束仍未找到匹配，返回-1。

（三）优缺点分析

-优点：实现简单，易于理解。

-缺点：时间复杂度较高（O(nm)），效率低，尤其当模式串较长或主串中存在大量不匹配时。

---

三、KMP算法

KMP算法（Knuth-Morris-Pratt）是对暴力匹配的改进，通过预处理模式串构建部分匹配表（Next数组），避免主串指针的无效回溯，从而提高匹配效率。

（一）算法原理

KMP的核心在于利用模式串自身的重复模式，当不匹配发生时，根据部分匹配表直接跳转至更合适的位置继续比较，无需回溯主串。

（二）实现步骤

1.构建Next数组：

-`Next[j]`表示模式串`pattern[0..j]`的最长前缀与后缀相等的长度。

-步骤：

-初始化`Next[0]=-1`，`Next[1]=0`。

-使用双指针`i`和`k`遍历模式串，计算`Next[j]`。

2.字符串匹配：

-初始化主串指针`i`和模式串指针`j`为0。

-遍历主串，若`text[i]==pattern[j]`，则`i++`，`j++`。

-若`j`等于模式串长度，返回匹配位置`i-j`。

-若不匹配且`j>0`，则将`j`更新为`Next[j-1]`，继续比较。

-若`j==0`，则`i++`，继续匹配。

3.匹配失败：若主串遍历完毕仍未匹配，返回-1。

（三）优缺点分析

-优点：时间复杂度降低至O(n)，无回溯主串。

-缺点：Next数组的构建需要额外空间和计算，实现相对复杂。

---

四、Boyer-Moore算法

Boyer-Moore算法是一种高效的后缀匹配算法，通过分析模式串，构建坏字符规则和好后缀规则，优先跳过最不可能匹配的字符，从而加速搜索过程。

（一）算法原理

Boyer-Moore利用两种规则：

1.坏字符规则：基于模式串中字符最后出现的位置，若当前字符不匹配，则将模式串右移至坏字符右侧。

2.好后缀规则：若主串中存在模式串的后缀与前面部分完全匹配，则将模式串右移至匹配后缀右侧。

（二）实现步骤

1.坏字符表构建：

-遍历模式串，记录每个字符最后出现的位置。

-若字符未出现，则位置设为-1。

2.好后缀表构建：

-通过模式串倒序遍历，计算每个后缀的最长匹配前缀长度。

3.字符串匹配：

-初始化主串指针`i`和模式串指针`j`为模式串长度减1。

-若`text[i]==pattern[j]`，则`i--`，`j--`。

-若`j==-1`，返回匹配位置`i+1`。

-若不匹配，根据坏字符规则或好后缀规则计算跳转步长，更新`i`和`j`。

4.匹配失败：若主串遍历完毕仍未匹配，返回-1。

（三）优缺点分析

-优点：平均时间复杂度较低（O(n)），尤其在模式串较长时效率显著。

-缺点：规则构建复杂，最坏情况下仍为O(nm)。

---

五、总结

字符串匹配算法的选择需根据实际应用场景权衡效率与实现复杂度：

-暴力匹配适用于简单场景或小规模数据。

-KMP算法在避免主串回溯方面表现优异，适用于通用匹配。

-Boyer-Moore算法在模式串较长时效率最高，但实现复杂。实际应用中，可根据需求选择合适的算法或结合多种方法优化性能。

三、KMP算法（续）

（二）实现步骤（续）

1.构建Next数组（续）

-Next数组的含义：`Next[j]`的值表示当模式串`pattern`的第`j`个字符与主串`text`中的字符不匹配时，模式串应回退到的位置`j'`（即`pattern[j']`与`text[i]`再次进行比较）。这个位置`j'`是基于模式串前`j`个字符的最长公共前后缀长度确定的。

-计算Next数组的详细步骤：

-初始化：

-创建一个数组`Next`，长度与模式串`pattern`相同，初始全部填充为-1。

-设置`Next[0]=-1`，因为单个字符没有前缀和后缀，其最长公共前后缀长度为0（用-1表示）。

-设置`Next[1]=0`，因为两个字符的最长公共前后缀长度为0（用0表示）。

-双指针遍历模式串：

-设置两个指针`i`和`k`，初始`i=2`（从模式的第二个字符开始），`k=0`（表示当前比较的前缀长度）。

-进入循环，条件为`i<m`（`m`是模式串长度）。

-比较`pattern[i-1]`和`pattern[k]`：

-如果`pattern[i-1]==pattern[k]`：

-说明找到了一个更长的公共前后缀，将`k`加1，然后`Next[i]=k`。

-`i`再加1，继续处理下一个字符。

-如果`pattern[i-1]!=pattern[k]`：

-这时需要回溯`k`，将`k`设置为`Next[k]`。

-比较`pattern[i-1]`和`pattern[k]`，重复上述过程，直到满足以下两种情况之一：

-`k`等于-1：说明当前字符`pattern[i-1]`没有匹配的前缀（除了它自己），此时`Next[i]=0`，`i`加1。

-`pattern[i-1]==pattern[k]`：找到匹配，`Next[i]=k+1`，`i`加1。

-循环结束后，`Next`数组构建完成。

-Next数组的示例：

-以模式串`pattern="ABABCABAA"`为例：

-`Next=[-1,0,0,1,2,0,1,2,3,4]`

-解释：

-`Next[0]=-1`：单个字符"A"没有前后缀。

-`Next[1]=0`：字符"AB"没有公共前后缀。

-`Next[2]=0`：字符"ABA"没有公共前后缀。

-`Next[3]=1`："ABA"的最长公共前后缀是"A"。

-`Next[4]=2`："ABAB"的最长公共前后缀是"AB"。

-`Next[5]=0`："ABABC"与前面不匹配，重置。

-`Next[6]=1`："ABABCAB"的最长公共前后缀是"A"。

-`Next[7]=2`："ABABCABA"的最长公共前后缀是"AB"。

-`Next[8]=3`："ABABCABAA"的最长公共前后缀是"ABA"。

-`Next[9]=4`："ABABCABAA"的最长公共前后缀是"ABAB"。

2.字符串匹配（续）

-初始化：

-设置主串指针`i`为0，模式串指针`j`为0。

-主循环：

-遍历主串`text`，直到`i<n-m+1`（`n`为主串长度）。

-比较`text[i+j]`和`pattern[j]`：

-如果相等，`j`加1，继续比较下一个字符。

-如果`j`等于模式串长度`m`，说明匹配成功，返回`i`（当前匹配起始位置）。

-如果不相等，需要进行回溯：

-如果`j>0`，根据`Next[j-1]`更新`j`的值：

-`j=Next[j-1]`。

-这是因为`Next[j-1]`表示模式串前`j-1`个字符的最长公共前后缀长度，即模式串应回退到的位置。

-如果`j==0`，说明当前字符`text[i]`与模式串的第一个字符不匹配，将`i`加1，继续下一个位置的比较。

-匹配失败：

-如果主串遍历完毕仍未找到匹配，返回-1。

3.匹配失败时的处理

-当匹配失败时，KMP算法不会回溯主串指针`i`，而是利用Next数组快速确定模式串指针`j`的下一个比较位置。

-这种方式避免了暴力匹配中大量无效的主串回溯，提高了匹配效率。

-例如，在模式串"ABABCABAA"与主串"ABABABCABAAABABCABAA"的匹配中：

-当比较到主串的某个位置时，如果发生不匹配，KMP算法会根据Next数组将模式串右移，使得模式串的一个前缀与主串中当前位置的前缀对齐，从而继续比较。

（三）优缺点分析（续）

-优点（续）：

-时间效率高：KMP算法的平均时间复杂度为O(n)，其中n为主串长度。这是因为算法在发生不匹配时不会回溯主串指针，而是通过Next数组快速确定下一个比较位置。

-空间效率适中：Next数组的空间复杂度为O(m)，其中m为模式串长度。相对于暴力匹配，空间开销增加不大。

-通用性强：KMP算法适用于各种模式串和主串的匹配场景，特别是当模式串中存在较多重复子串时，效率优势明显。

-缺点（续）：

-实现复杂度较高：Next数组的构建需要一定的算法技巧和代码实现能力，相比暴力匹配，代码量更大，调试难度也更高。

-Next数组构建时间：虽然Next数组的构建时间复杂度为O(m)，但在某些极端情况下，如果模式串具有特殊的结构（如大量重复字符），构建过程可能会相对耗时。

-最坏情况时间复杂度：虽然在平均情况下时间复杂度为O(n)，但在最坏情况下（如主串与模式串只有部分字符匹配），时间复杂度仍可能退化到O(nm)。

四、Boyer-Moore算法（续）

（一）算法原理（续）

-坏字符规则（续）：

-坏字符的定义：在模式串`pattern`中，从右向左扫描，最后一个与主串`text`中当前字符不匹配的字符称为坏字符。

-跳转逻辑：当发生不匹配时，将模式串向右移动，使得坏字符在主串中的位置与模式串中相同字符的最近位置对齐。

-具体计算：如果坏字符在模式串中的位置为`k`，在主串中的位置为`j`，则模式串应向右移动`j-k-1`个位置。

-特殊情况：

-如果坏字符是模式串的第一个字符，则模式串至少向右移动1个位置。

-如果坏字符在模式串中不存在，则模式串可以移动到主串的下一个位置。

-好后缀规则（续）：

-好后缀的定义：在模式串`pattern`中，一个子串如果作为后缀与主串`text`中当前字符之前的子串完全匹配，则称这个子串为好后缀。

-跳转逻辑：当发生不匹配时，将模式串向右移动，使得好后缀在主串中的位置与模式串中相同好后缀的最近位置对齐。

-具体计算：

-首先找到模式串中与当前不匹配字符之后的最长好后缀。

-然后找到主串中该好后缀的下一个位置。

-模式串应移动到该位置。

-特殊情况：

-如果没有好后缀，则采用坏字符规则进行跳转。

-如果好后缀是整个模式串，则模式串向右移动1个位置。

-两种规则的优先级：

-Boyer-Moore算法通常优先使用好后缀规则，因为好后缀规则可以提供更大的跳转距离，从而提高匹配效率。

-只有在找不到好后缀或好后缀规则无法提供更大的跳转距离时，才使用坏字符规则。

（二）实现步骤（续）

1.坏字符表的构建（续）

-坏字符表的定义：创建一个数组`bad_char`，长度为字符集的大小（例如，ASCII字符集为128），用于存储每个字符在模式串中最后出现的位置。

-构建步骤：

-遍历模式串`pattern`，从右向左扫描。

-对于每个字符`c`，将其在模式串中的位置存储到`bad_char[c]`中。

-如果字符`c`在模式串中不存在，则将其位置设为-1。

-坏字符表的作用：当发生不匹配时，可以根据坏字符表快速确定模式串的跳转位置。

2.好后缀表的构建（续）

-好后缀表的定义：创建一个数组`good_suffix`，长度与模式串相同，用于存储每个位置上的好后缀信息。

-构建步骤：

-使用一个辅助函数`好后缀匹配长度(j)`，该函数返回模式串`pattern`中从位置`j`开始的最长好后缀与模式串前缀相匹配的长度。

-遍历模式串`pattern`，从右向左扫描，对于每个位置`j`，计算`好后缀匹配长度(j)`，并将结果存储到`good_suffix[j]`中。

-具体计算方法可以使用后缀数组或双指针法。

-好后缀表的作用：当发生不匹配时，可以根据好后缀表快速确定模式串的跳转位置。

3.字符串匹配（续）

-初始化：

-设置主串指针`i`为模式串长度`m`减1（因为Boyer-Moore算法从右向左比较）。

-设置模式串指针`j`为模式串长度`m`减1。

-主循环：

-比较`text[i]`和`pattern[j]`：

-如果相等，`j`减1，`i`减1，继续比较下一个字符。

-如果`j`等于-1，说明匹配成功，返回匹配起始位置`i+1`。

-如果不相等，需要进行跳转：

-首先使用好后缀规则进行跳转：

-如果`j`大于0，计算`good_suffix[j]`。

-如果`good_suffix[j]`大于0，将模式串向右移动`j-good_suffix[j]`个位置。

-否则，使用坏字符规则进行跳转。

-如果好后缀规则无法提供跳转，使用坏字符规则进行跳转：

-计算坏字符在模式串中的位置`k`。

-计算跳转距离`shift=j-k-1`。

-如果`shift`小于0，则模式串向右移动1个位置。

-否则，模式串向右移动`shift`个位置。

-匹配失败：

-如果主串遍历完毕仍未找到匹配，返回-1。

4.匹配失败时的处理

-当匹配失败时，Boyer-Moore算法会根据好后缀规则或坏字符规则快速确定模式串的下一个比较位置。

-这种方式避免了暴力匹配和KMP算法中的一些无效比较，从而提高了匹配效率。

-例如，在模式串"ABABCABAA"与主串"ABABABCABAAABABCABAA"的匹配中：

-当比较到主串的某个位置时，如果发生不匹配，Boyer-Moore算法会根据好后缀规则或坏字符规则将模式串右移，使得模式串的一个前缀与主串中当前位置的前缀对齐，从而继续比较。

（三）优缺点分析（续）

-优点（续）：

-极高的平均时间效率：Boyer-Moore算法的平均时间复杂度接近O(n/m)，其中n为主串长度，m为模式串长度。这是因为算法在发生不匹配时可以跳过大量字符，特别是当模式串较长时，效率优势明显。

-良好的最坏情况性能：虽然Boyer-Moore算法的最坏情况时间复杂度仍为O(nm)，但在实际应用中，这种情况很少发生，因此算法的整体性能表现优秀。

-灵活的规则选择：Boyer-Moore算法结合了坏字符规则和好后缀规则，可以根据不同的模式串和主串选择最合适的跳转方式。

-缺点（续）：

-实现复杂度较高：Boyer-Moore算法的实现比暴力匹配和KMP算法更复杂，需要构建坏字符表和好后缀表，代码量更大，调试难度也更高。

-预处理的额外开销：构建坏字符表和好后缀表需要额外的空间和时间，对于非常短的模式串，这种预处理的额外开销可能会抵消算法的时间效率优势。

-对字符集敏感：Boyer-Moore算法的性能很大程度上取决于字符集的大小和模式串中字符的分布。在字符集较小或模式串中字符分布不均匀时，算法的效率可能会下降。

五、总结（续）

字符串匹配算法的选择需要综合考虑多种因素，包括模式串和主串的长度、字符集的大小、匹配的频率以及对效率的要求等。

-暴力匹配：简单易实现，适用于小规模数据或对效率要求不高的场景。

-KMP算法：时间效率高，通用性强，适用于大多数匹配场景，特别是当模式串中存在较多重复子串时。

-Boyer-Moore算法：平均时间效率最高，适用于模式串较长且对效率要求较高的场景。

实际应用中，可以根据具体需求选择合适的算法，或结合多种方法优化性能。例如，对于非常短的模式串，暴力匹配可能更简单高效；对于中等长度的模式串，KMP算法是一个不错的选择；而对于长模式串，Boyer-Moore算法通常能提供最佳的性能。此外，还可以考虑使用一些自适应的字符串匹配算法，这些算法可以根据匹配过程中的实际情况动态调整匹配策略，进一步提高效率。

一、概述

字符串匹配算法是计算机科学中的一项基础技术，广泛应用于文本处理、数据检索、信息安全等领域。其核心任务是在一个较长的文本串（主串）中查找是否存在一个较短的子串（模式串），并返回子串在主串中的起始位置。根据不同的应用场景和性能要求，存在多种字符串匹配算法，如暴力匹配、KMP算法、Boyer-Moore算法等。本文档将详细介绍几种典型字符串匹配算法的实现细节，包括其原理、步骤及优缺点分析。

---

二、暴力匹配算法

暴力匹配算法是最基础的字符串匹配方法，其基本思想是逐个比较模式串与主串中每个可能的子串，直到找到匹配或遍历完主串。

（一）算法原理

暴力匹配的核心是通过双层循环实现：外层循环遍历主串的每个字符，内层循环逐个比较模式串与主串的子串。若所有字符匹配成功，则返回匹配位置；若遇到不匹配，则内层循环终止，外层循环移动到下一个位置继续比较。

（二）实现步骤

1.初始化：设置主串指针`i`从0开始，模式串指针`j`也从0开始。

2.外层循环：遍历主串，`i`从0到`n-m`（`n`为主串长度，`m`为模式串长度）。

3.内层循环：逐个比较主串`text[i..i+m-1]`与模式串`pattern[0..m-1]`。

-若字符匹配（`text[i+j]==pattern[j]`），则`j`加1。

-若`j`等于模式串长度，说明匹配成功，返回`i`。

-若字符不匹配，重置`j`为0，`i`加1。

4.匹配失败：若外层循环结束仍未找到匹配，返回-1。

（三）优缺点分析

-优点：实现简单，易于理解。

-缺点：时间复杂度较高（O(nm)），效率低，尤其当模式串较长或主串中存在大量不匹配时。

---

三、KMP算法

KMP算法（Knuth-Morris-Pratt）是对暴力匹配的改进，通过预处理模式串构建部分匹配表（Next数组），避免主串指针的无效回溯，从而提高匹配效率。

（一）算法原理

KMP的核心在于利用模式串自身的重复模式，当不匹配发生时，根据部分匹配表直接跳转至更合适的位置继续比较，无需回溯主串。

（二）实现步骤

1.构建Next数组：

-`Next[j]`表示模式串`pattern[0..j]`的最长前缀与后缀相等的长度。

-步骤：

-初始化`Next[0]=-1`，`Next[1]=0`。

-使用双指针`i`和`k`遍历模式串，计算`Next[j]`。

2.字符串匹配：

-初始化主串指针`i`和模式串指针`j`为0。

-遍历主串，若`text[i]==pattern[j]`，则`i++`，`j++`。

-若`j`等于模式串长度，返回匹配位置`i-j`。

-若不匹配且`j>0`，则将`j`更新为`Next[j-1]`，继续比较。

-若`j==0`，则`i++`，继续匹配。

3.匹配失败：若主串遍历完毕仍未匹配，返回-1。

（三）优缺点分析

-优点：时间复杂度降低至O(n)，无回溯主串。

-缺点：Next数组的构建需要额外空间和计算，实现相对复杂。

---

四、Boyer-Moore算法

Boyer-Moore算法是一种高效的后缀匹配算法，通过分析模式串，构建坏字符规则和好后缀规则，优先跳过最不可能匹配的字符，从而加速搜索过程。

（一）算法原理

Boyer-Moore利用两种规则：

1.坏字符规则：基于模式串中字符最后出现的位置，若当前字符不匹配，则将模式串右移至坏字符右侧。

2.好后缀规则：若主串中存在模式串的后缀与前面部分完全匹配，则将模式串右移至匹配后缀右侧。

（二）实现步骤

1.坏字符表构建：

-遍历模式串，记录每个字符最后出现的位置。

-若字符未出现，则位置设为-1。

2.好后缀表构建：

-通过模式串倒序遍历，计算每个后缀的最长匹配前缀长度。

3.字符串匹配：

-初始化主串指针`i`和模式串指针`j`为模式串长度减1。

-若`text[i]==pattern[j]`，则`i--`，`j--`。

-若`j==-1`，返回匹配位置`i+1`。

-若不匹配，根据坏字符规则或好后缀规则计算跳转步长，更新`i`和`j`。

4.匹配失败：若主串遍历完毕仍未匹配，返回-1。

（三）优缺点分析

-优点：平均时间复杂度较低（O(n)），尤其在模式串较长时效率显著。

-缺点：规则构建复杂，最坏情况下仍为O(nm)。

---

五、总结

字符串匹配算法的选择需根据实际应用场景权衡效率与实现复杂度：

-暴力匹配适用于简单场景或小规模数据。

-KMP算法在避免主串回溯方面表现优异，适用于通用匹配。

-Boyer-Moore算法在模式串较长时效率最高，但实现复杂。实际应用中，可根据需求选择合适的算法或结合多种方法优化性能。

三、KMP算法（续）

（二）实现步骤（续）

1.构建Next数组（续）

-Next数组的含义：`Next[j]`的值表示当模式串`pattern`的第`j`个字符与主串`text`中的字符不匹配时，模式串应回退到的位置`j'`（即`pattern[j']`与`text[i]`再次进行比较）。这个位置`j'`是基于模式串前`j`个字符的最长公共前后缀长度确定的。

-计算Next数组的详细步骤：

-初始化：

-创建一个数组`Next`，长度与模式串`pattern`相同，初始全部填充为-1。

-设置`Next[0]=-1`，因为单个字符没有前缀和后缀，其最长公共前后缀长度为0（用-1表示）。

-设置`Next[1]=0`，因为两个字符的最长公共前后缀长度为0（用0表示）。

-双指针遍历模式串：

-设置两个指针`i`和`k`，初始`i=2`（从模式的第二个字符开始），`k=0`（表示当前比较的前缀长度）。

-进入循环，条件为`i<m`（`m`是模式串长度）。

-比较`pattern[i-1]`和`pattern[k]`：

-如果`pattern[i-1]==pattern[k]`：

-说明找到了一个更长的公共前后缀，将`k`加1，然后`Next[i]=k`。

-`i`再加1，继续处理下一个字符。

-如果`pattern[i-1]!=pattern[k]`：

-这时需要回溯`k`，将`k`设置为`Next[k]`。

-比较`pattern[i-1]`和`pattern[k]`，重复上述过程，直到满足以下两种情况之一：

-`k`等于-1：说明当前字符`pattern[i-1]`没有匹配的前缀（除了它自己），此时`Next[i]=0`，`i`加1。

-`pattern[i-1]==pattern[k]`：找到匹配，`Next[i]=k+1`，`i`加1。

-循环结束后，`Next`数组构建完成。

-Next数组的示例：

-以模式串`pattern="ABABCABAA"`为例：

-`Next=[-1,0,0,1,2,0,1,2,3,4]`

-解释：

-`Next[0]=-1`：单个字符"A"没有前后缀。

-`Next[1]=0`：字符"AB"没有公共前后缀。

-`Next[2]=0`：字符"ABA"没有公共前后缀。

-`Next[3]=1`："ABA"的最长公共前后缀是"A"。

-`Next[4]=2`："ABAB"的最长公共前后缀是"AB"。

-`Next[5]=0`："ABABC"与前面不匹配，重置。

-`Next[6]=1`："ABABCAB"的最长公共前后缀是"A"。

-`Next[7]=2`："ABABCABA"的最长公共前后缀是"AB"。

-`Next[8]=3`："ABABCABAA"的最长公共前后缀是"ABA"。

-`Next[9]=4`："ABABCABAA"的最长公共前后缀是"ABAB"。

2.字符串匹配（续）

-初始化：

-设置主串指针`i`为0，模式串指针`j`为0。

-主循环：

-遍历主串`text`，直到`i<n-m+1`（`n`为主串长度）。

-比较`text[i+j]`和`pattern[j]`：

-如果相等，`j`加1，继续比较下一个字符。

-如果`j`等于模式串长度`m`，说明匹配成功，返回`i`（当前匹配起始位置）。

-如果不相等，需要进行回溯：

-如果`j>0`，根据`Next[j-1]`更新`j`的值：

-`j=Next[j-1]`。

-这是因为`Next[j-1]`表示模式串前`j-1`个字符的最长公共前后缀长度，即模式串应回退到的位置。

-如果`j==0`，说明当前字符`text[i]`与模式串的第一个字符不匹配，将`i`加1，继续下一个位置的比较。

-匹配失败：

-如果主串遍历完毕仍未找到匹配，返回-1。

3.匹配失败时的处理

-当匹配失败时，KMP算法不会回溯主串指针`i`，而是利用Next数组快速确定模式串指针`j`的下一个比较位置。

-这种方式避免了暴力匹配中大量无效的主串回溯，提高了匹配效率。

-例如，在模式串"ABABCABAA"与主串"ABABABCABAAABABCABAA"的匹配中：

-当比较到主串的某个位置时，如果发生不匹配，KMP算法会根据Next数组将模式串右移，使得模式串的一个前缀与主串中当前位置的前缀对齐，从而继续比较。

（三）优缺点分析（续）

-优点（续）：

-时间效率高：KMP算法的平均时间复杂度为O(n)，其中n为主串长度。这是因为算法在发生不匹配时不会回溯主串指针，而是通过Next数组快速确定下一个比较位置。

-空间效率适中：Next数组的空间复杂度为O(m)，其中m为模式串长度。相对于暴力匹配，空间开销增加不大。

-通用性强：KMP算法适用于各种模式串和主串的匹配场景，特别是当模式串中存在较多重复子串时，效率优势明显。

-缺点（续）：

-实现复杂度较高：Next数组的构建需要一定的算法技巧和代码实现能力，相比暴力匹配，代码量更大，调试难度也更高。

-Next数组构建时间：虽然Next数组的构建时间复杂度为O(m)，但在某些极端情况下，如果模式串具有特殊的结构（如大量重复字符），构建过程可能会相对耗时。

-最坏情况时间复杂度：虽然在平均情况下时间复杂度为O(n)，但在最坏情况下（如主串与模式串只有部分字符匹配），时间复杂度仍可能退化到O(nm)。

四、Boyer-Moore算法（续）

（一）算法原理（续）

-坏字符规则（续）：

-坏字符的定义：在模式串`pattern`中，从右向左扫描，最后一个与主串`text`中当前字符不匹配的字符称为坏字符。

-跳转逻辑：当发生不匹配时，将模式串向右移动，使得坏字符在主串中的位置与模式串中相同字符的最近位置对齐。

-具体计算：如果坏字符在模式串中的位置为`k`，在主串中的位置为`j`，则模式串应向右移动`j-k-1`个位置。

-特殊情况：

-如果坏字符是模式串的第一个字符，则模式串至少向右移动1个位置。

-如果坏字符在模式串中不存在，则模式串可以移动到主串的下一个位置。

-好后缀规则（续）：

-好后缀的定义：在模式串`pattern`中，一个子串如果作为后缀与主串`text`中当前字符之前的子串完全匹配，则称这个子串为好后缀。

-跳转逻辑：当发生不匹配时，将模式串向右移动，使得好后缀在主串中的位置与模式串中相同好后缀的最近位置对齐。

-具体计算：

-首先找到模式串中与当前不匹配字符之后的最长好后缀。

-然后找到主串中该好后缀的下一个位置。

-模式串应移动到该位置。

-特殊情况：

-如果没有好后缀，则采用坏字符规则进行跳转。

-如果好后缀是整个模式串，则模式串向右移动1个位置。

-两种规则的优先级：

-Boyer-Moore算法通常优先使用好后缀规则，因为好后缀规则可以提供更大的跳转距离，从而提高匹配效率。

-只有在找不到好后缀或好后缀规则无法提供更大的跳转距离时，才使用坏字符规则。

（二）实现步骤（续）

1.坏字符表的构建（续）

-坏字符表的定义：创建一个数组`bad_char`，长度为字符集的大小（例如，ASCII字符集为128），用于存储每个字符在模式串中最后出现的位置。

-构建步骤：

-遍历模式串`pattern`，从右向左扫描。

-对于每个字符`c`，将其在模式串中的位置存储到`bad_char[c]`中。

-如果字符`c`在模式串中不存在，则将其位置设为-1。

-坏字符表的作用：当发生不匹配时，可以根据坏字符表快速确定模式串的跳转位置。

2.好后缀表的构建（续）

-好后缀表的定义：创建一个数组`good_suffix`，长度与模式串相同，用于存储每个位置上的好后缀信息。

-构建步骤：

-使用一个辅助函数`好后缀匹配长度(j)`，该函数返回模式串`pattern`中从位置`j`开始的最长好后缀与模式串前缀相匹配的长度。

-遍历模式串`pattern`，从右向左扫描，对于每个位置`j`，计算`好后缀匹配长度(j)`，并将结果存储到`good_suffix[j]`中。

-具体计算方法可以使用后缀数组或双指针法。

-好后缀表的作用：当发生不匹配时，可以根据好后缀表快速确定模式串的跳转位置。

3.字符串匹配（续）

-初始化：

-设置主串指针`i`为模式串长度`m`减1（因为Boyer-Moore算法从右向左比较）。

-设置模式串指针`j`为模式串长度`m`减1。

-主循环：

-比较`text[i]`和`pattern[j]`：

-如果相等，`j`减1，`i`减1