字符串匹配算法的模式匹配原理

字符串匹配算法的模式匹配原理一、引言

字符串匹配算法是计算机科学中常见的算法问题，其核心目标是在一个较长的文本串（主串）中查找是否存在一个较短的子串（模式串），并返回子串在主串中的起始位置。模式匹配原理涉及多种方法，包括朴素匹配、KMP算法、Boyer-Moore算法等。本文档将重点介绍朴素匹配算法和KMP算法的基本原理、实现步骤及优缺点分析。

二、朴素匹配算法（Brute-ForceAlgorithm）

朴素匹配算法是最直观的字符串匹配方法，其基本思想是：从主串和模式串的第一个字符开始，依次比较两个串的字符是否相同，若相同则继续比较下一个字符，若不同则主串指针回退到上一个匹配位置的后一个字符，模式串指针回退到第一个字符，重新开始匹配。

（一）算法步骤

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

2.匹配过程：

-比较`text[i]`和`pattern[j]`是否相同。

-若相同，`i`和`j`均加1，继续比较下一个字符。

-若不同，`i`回退到`i-j+1`，`j`重置为0。

3.终止条件：

-若`j`达到模式串长度`m`，则匹配成功，返回`i-m`（匹配起始位置）。

-若`i`超过主串长度`n`仍未匹配成功，则匹配失败，返回-1。

（二）示例

假设主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`：

1.初始：`i=0,j=0`，比较`'A'=='A'`，`i=1,j=1`，比较`'B'=='B'`，...

2.到`i=9,j=8`时，`'E'!='E'`，回退`i=5,j=0`，重新匹配。

3.最终匹配成功，起始位置为5。

（三）时间复杂度

-最好情况：O(n)，模式串第一个字符即匹配成功。

-最坏情况：O(nm)，模式串每个字符均需比较。

-平均情况：O(nm)。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是对朴素匹配的优化，通过预处理模式串，避免主串指针的无效回退，从而将时间复杂度降低至O(n)。

（一）核心思想

KMP算法的核心是构建一个“部分匹配表”（Next数组），用于记录模式串的前缀和后缀相同长度的最大值。当不匹配发生时，利用该表跳过已知的无效前缀，直接从有效位置继续匹配。

（二）Next数组构建

Next数组的计算步骤如下：

1.初始化：`next[0]=-1`，`next[1]=0`。

2.从`i=2`开始，遍历模式串：

-若`pattern[i-1]==pattern[next[i-1]]`，则`next[i]=next[i-1]+1`。

-否则，回退`k=next[next[i-1]]`，比较`pattern[i-1]==pattern[k]`，重复直到找到匹配或`k=-1`。

-若无匹配，`next[i]=0`。

示例：模式串`"ABCDABE"`的Next数组为`[-1,0,0,0,1,2,3]`。

（三）匹配过程

1.初始化：主串指针`i=0`，模式串指针`j=0`。

2.比较`text[i]`和`pattern[j]`：

-若相同，`i++,j++`。

-若`j==m`，匹配成功，返回`i-j`。

-若不匹配且`j>0`，更新`j=next[j]`（利用Next数组跳转）。

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

3.匹配失败返回-1。

（四）时间复杂度

-构建Next数组：O(m)。

-匹配过程：O(n)。

-总体时间复杂度：O(n+m)。

四、Boyer-Moore算法简介

Boyer-Moore算法是另一种高效的模式匹配算法，其核心思想是通过“坏字符规则”和“好后缀规则”跳过大量无效比较，时间复杂度可达O(n/m)。

-坏字符规则：基于模式串中不匹配的字符，计算最大可跳转距离。

-好后缀规则：基于模式串中匹配的后缀，计算最大可跳转距离。

Boyer-Moore算法适用于长模式串，但实现相对复杂，此处不作详细展开。

五、总结

字符串匹配算法的选择取决于实际应用场景：

-朴素匹配：简单易实现，适用于小规模数据。

-KMP算法：通用性强，效率高，适合大规模文本处理。

-Boyer-Moore算法：速度最快，但实现复杂，适用于长模式串。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是对朴素匹配的优化，通过预处理模式串，避免主串指针的无效回退，从而将时间复杂度降低至O(n)。其核心在于利用模式串自身的特性，在发生不匹配时，尽可能多地跳过已经确认不会匹配的部分，从而提高匹配效率。KMP算法主要由两部分组成：部分匹配表的构建（Next数组的生成）和基于部分匹配表的匹配过程。

（一）核心思想与优势

KMP算法的核心思想是：当模式串与主串在某位置发生不匹配时，不需要将主串的指针回退到模式串指针之前的位置，而是利用已经计算出的模式串的部分匹配信息，将模式串向后滑动，使其在主串中的某个位置与之前匹配成功的部分对齐，从而继续比较。这种做法避免了主串指针的多次回退，显著提高了算法的效率。

KMP算法的优势主要体现在以下方面：

1.时间效率高：在最好和平均情况下，时间复杂度为O(n)，远优于朴素匹配的O(nm)。

2.空间复杂度可控：Next数组的构建需要额外的空间，但其空间复杂度为O(m)，其中m是模式串的长度。

3.通用性强：适用于多种字符串匹配场景，特别是当模式串较长或主串中存在大量重复子串时，性能优势更为明显。

（二）部分匹配表（Next数组）的构建

部分匹配表是KMP算法的关键，它记录了模式串的前缀和后缀的最长相同子串的长度。通过该表，可以在不匹配发生时，确定模式串应该滑动的位置。部分匹配表的构建过程如下：

1.初始化：

-创建一个与模式串等长的数组`Next`，用于存储部分匹配信息。

-初始化`Next[0]=-1`，因为单个字符的前缀和后缀不可能相同。

-设置指针`i`从1开始遍历模式串，`k`为当前`i`的前一个位置的最长相同子串长度（即`Next[k]`）。

2.遍历模式串，填充Next数组：

-对于每个位置`i`（从1到m-1），执行以下步骤：

(1)比较当前字符与前缀的最长相同子串的最后一个字符：

-若`pattern[i-1]==pattern[k]`，则说明当前前缀和后缀的最长相同子串长度加1，即`Next[i]=k+1`，然后`i++`和`k++`继续比较下一个字符。

-若不匹配，则需要更新`k`的值：将`k`设置为`Next[k-1]`，即回退到前一个最长相同子串的前一个位置，重复比较，直到`k==-1`或`pattern[i-1]==pattern[k]`。

(2)处理不匹配的情况：

-若`k==-1`，说明当前字符`pattern[i-1]`没有前缀和后缀相同的情况，因此`Next[i]=0`，然后`i++`继续遍历。

(3)更新Next数组：

-每次比较后，若找到匹配，则`Next[i]=k+1`；若未找到，则`Next[i]=0`（当`k==-1`时）。

3.Next数组的含义：

-`Next[i]`表示模式串`pattern[0...i-1]`中，最长相等的前缀和后缀的长度。

-例如，模式串`"ABCDABE"`的Next数组为`[-1,0,0,0,1,2,3]`，表示：

-`pattern[0]`："A"→无前缀和后缀相同，`Next[0]=-1`。

-`pattern[0...1]`："AB"→无相同子串，`Next[1]=0`。

-`pattern[0...3]`："ABCD"→无相同子串，`Next[3]=0`。

-`pattern[0...4]`："ABCDAB"→"AB"=="AB"，`Next[4]=1`。

-`pattern[0...5]`："ABCDABE"→"AB"=="AB"，`Next[5]=2`。

-`pattern[0...6]`："ABCDABE"→"ABCD"=="ABCD"，`Next[6]=3`。

（三）基于部分匹配表的匹配过程

在构建完Next数组后，即可开始匹配过程。匹配过程中，主串指针`i`和模式串指针`j`分别从0开始遍历，当字符匹配时，两者同时后移；当不匹配时，利用Next数组确定模式串的滑动位置。具体步骤如下：

1.初始化：

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

2.遍历主串和模式串：

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

(1)若相同：

-`i++`，`j++`，继续比较下一个字符。

-若`j==m`（模式串长度），则匹配成功，返回`i-j`（匹配起始位置）。

(2)若不同：

-若`j>0`，则将模式串指针`j`更新为`Next[j]`，即利用Next数组跳转。

-若`j==0`，说明当前匹配失败，仅移动主串指针`i++`，继续匹配下一个位置。

3.匹配失败：

-若遍历完主串仍未匹配成功（即`i==n`且未返回匹配位置），则返回-1表示不存在匹配。

4.示例：

-主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`，Next数组为`[-1,0,0,0,1,2,3]`。

-匹配过程：

-`i=0,j=0`，比较`'A'=='A'`，`i=1,j=1`。

-`i=2,j=2`，比较`'B'=='B'`，`i=3,j=3`。

-`i=4,j=4`，比较`'C'=='C'`，`i=5,j=5`。

-`i=6,j=6`，比较`'D'=='D'`，`i=7,j=7`。

-`i=8,j=8`，比较`'A'!='E'`，`j`更新为`Next[8]=3`（跳转至`'CDABE'`）。

-`i=8,j=3`，比较`'A'=='A'`，`i=9,j=4`。

-`i=10,j=5`，比较`'B'=='B'`，`i=11,j=6`。

-`i=12,j=7`，比较`'E'=='E'`，`j==m`，匹配成功，返回`i-j=5`。

（四）时间复杂度分析

1.Next数组的构建：

-遍历模式串一次，每次比较和更新Next数组的时间复杂度为O(1)，因此总时间复杂度为O(m)。

2.匹配过程：

-主串和模式串各遍历一次，每次比较和指针更新操作的时间复杂度为O(1)，因此总时间复杂度为O(n)。

3.总体时间复杂度：

-O(m)+O(n)=O(n+m)，即线性时间复杂度。

（五）空间复杂度分析

-Next数组占用O(m)的额外空间，因此KMP算法的空间复杂度为O(m)。

（六）适用场景

KMP算法适用于以下场景：

1.模式串较长：当模式串长度m较大时，KMP算法的效率优势明显。

2.主串中存在大量重复子串：KMP算法能够有效利用重复子串的信息，减少不必要的比较。

3.需要多次匹配同一模式串：Next数组的预处理可以在多次匹配时复用，提高效率。

四、Boyer-Moore算法简介

Boyer-Moore算法是另一种高效的字符串匹配算法，其核心思想是通过“坏字符规则”和“好后缀规则”跳过大量无效比较，时间复杂度可达O(n/m)。该算法在模式串较长时表现优异，但实现相对复杂，因此此处仅作简要介绍。

（一）坏字符规则（BadCharacterRule）

坏字符规则基于模式串中不匹配的字符，计算模式串可以滑动的最大距离。具体步骤如下：

1.坏字符表构建：

-创建一个坏字符表，记录模式串中每个字符最后出现的位置。若字符未出现，则记录为-1。

2.匹配过程中的坏字符处理：

-当主串和模式串在某位置不匹配时，找到模式串中与主串不匹配的字符（坏字符）。

-根据坏字符表，计算模式串可滑动的距离：

-若坏字符在模式串中不存在（位置为-1），则模式串可以滑动到主串的下一个位置。

-若坏字符存在，则模式串滑动到坏字符在主串中的位置之后。

-若坏字符在模式串中有多个，则选择最右边的坏字符进行滑动。

3.示例：

-模式串`"ABCDABE"`，坏字符表：`{'A':6,'B':5,'C':4,'D':3,'E':7,'F':-1}`。

-主串`"ABCDABCDABE"`，模式串滑动到`"ABCDABE"`时，`'E'`不匹配（坏字符为`'E'`，最后出现位置为7），模式串滑动到`'E'`之后，即从`"BCDABE"`开始继续匹配。

（二）好后缀规则（GoodSuffixRule）

好后缀规则基于模式串中匹配的后缀，计算模式串可以滑动的最大距离。该规则比坏字符规则更复杂，但可以跳过更多的无效比较。

1.好后缀表构建：

-创建一个好后缀表，记录模式串中每个后缀的最长相等前缀和后缀的长度。

2.匹配过程中的好后缀处理：

-当主串和模式串在某位置不匹配时，若不匹配位置之前的部分与模式串的后缀相同，则利用好后缀表确定模式串的滑动位置。

-具体滑动距离取决于好后缀表中记录的最长相等子串长度。

3.示例：

-模式串`"ABCDABE"`，好后缀表：`{-1,0,0,0,1,2,3}`（与KMP的Next数组类似，但含义不同）。

-主串`"ABCDABCDABE"`，模式串滑动到`"ABCDABE"`时，若`'E'`不匹配，可以利用好后缀表跳转至`"CDABE"`或`"DABE"`等位置继续匹配。

（三）Boyer-Moore算法的优势与劣势

优势：

1.高效率：在最好情况下，时间复杂度可达O(n/m)，远优于KMP算法。

2.适用于长模式串：当模式串长度m较大时，Boyer-Moore算法的效率优势明显。

劣势：

1.实现复杂：坏字符规则和好后缀规则的实现较为复杂，需要额外的空间存储坏字符表和好后缀表。

2.部分情况性能下降：当主串和模式串匹配度较高时，坏字符规则和好后缀规则的跳转效果可能不明显。

五、总结

字符串匹配算法的选择取决于实际应用场景和需求：

1.朴素匹配：

-适用场景：模式串较短，主串中重复子串较少，对效率要求不高。

-实现方式：简单直观，通过两层循环逐字符比较。

-时间复杂度：O(nm)。

2.KMP算法：

-适用场景：模式串较长，主串中存在大量重复子串，需要多次匹配同一模式串。

-实现方式：通过构建Next数组，避免主串指针的无效回退。

-时间复杂度：O(n+m)。

3.Boyer-Moore算法：

-适用场景：模式串较长，对匹配效率要求极高。

-实现方式：通过坏字符规则和好后缀规则跳过无效比较。

-时间复杂度：O(n/m)（最好情况）。

在实际应用中，可以根据具体需求选择合适的算法，或结合多种算法的优点进行优化。例如，对于长模式串且匹配次数较少的场景，Boyer-Moore算法可能更合适；而对于需要多次匹配同一模式串的场景，KMP算法的线性时间复杂度优势更为明显。

一、引言

字符串匹配算法是计算机科学中常见的算法问题，其核心目标是在一个较长的文本串（主串）中查找是否存在一个较短的子串（模式串），并返回子串在主串中的起始位置。模式匹配原理涉及多种方法，包括朴素匹配、KMP算法、Boyer-Moore算法等。本文档将重点介绍朴素匹配算法和KMP算法的基本原理、实现步骤及优缺点分析。

二、朴素匹配算法（Brute-ForceAlgorithm）

朴素匹配算法是最直观的字符串匹配方法，其基本思想是：从主串和模式串的第一个字符开始，依次比较两个串的字符是否相同，若相同则继续比较下一个字符，若不同则主串指针回退到上一个匹配位置的后一个字符，模式串指针回退到第一个字符，重新开始匹配。

（一）算法步骤

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

2.匹配过程：

-比较`text[i]`和`pattern[j]`是否相同。

-若相同，`i`和`j`均加1，继续比较下一个字符。

-若不同，`i`回退到`i-j+1`，`j`重置为0。

3.终止条件：

-若`j`达到模式串长度`m`，则匹配成功，返回`i-m`（匹配起始位置）。

-若`i`超过主串长度`n`仍未匹配成功，则匹配失败，返回-1。

（二）示例

假设主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`：

1.初始：`i=0,j=0`，比较`'A'=='A'`，`i=1,j=1`，比较`'B'=='B'`，...

2.到`i=9,j=8`时，`'E'!='E'`，回退`i=5,j=0`，重新匹配。

3.最终匹配成功，起始位置为5。

（三）时间复杂度

-最好情况：O(n)，模式串第一个字符即匹配成功。

-最坏情况：O(nm)，模式串每个字符均需比较。

-平均情况：O(nm)。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是对朴素匹配的优化，通过预处理模式串，避免主串指针的无效回退，从而将时间复杂度降低至O(n)。

（一）核心思想

KMP算法的核心是构建一个“部分匹配表”（Next数组），用于记录模式串的前缀和后缀相同长度的最大值。当不匹配发生时，利用该表跳过已知的无效前缀，直接从有效位置继续匹配。

（二）Next数组构建

Next数组的计算步骤如下：

1.初始化：`next[0]=-1`，`next[1]=0`。

2.从`i=2`开始，遍历模式串：

-若`pattern[i-1]==pattern[next[i-1]]`，则`next[i]=next[i-1]+1`。

-否则，回退`k=next[next[i-1]]`，比较`pattern[i-1]==pattern[k]`，重复直到找到匹配或`k=-1`。

-若无匹配，`next[i]=0`。

示例：模式串`"ABCDABE"`的Next数组为`[-1,0,0,0,1,2,3]`。

（三）匹配过程

1.初始化：主串指针`i=0`，模式串指针`j=0`。

2.比较`text[i]`和`pattern[j]`：

-若相同，`i++,j++`。

-若`j==m`，匹配成功，返回`i-j`。

-若不匹配且`j>0`，更新`j=next[j]`（利用Next数组跳转）。

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

3.匹配失败返回-1。

（四）时间复杂度

-构建Next数组：O(m)。

-匹配过程：O(n)。

-总体时间复杂度：O(n+m)。

四、Boyer-Moore算法简介

Boyer-Moore算法是另一种高效的模式匹配算法，其核心思想是通过“坏字符规则”和“好后缀规则”跳过大量无效比较，时间复杂度可达O(n/m)。

-坏字符规则：基于模式串中不匹配的字符，计算最大可跳转距离。

-好后缀规则：基于模式串中匹配的后缀，计算最大可跳转距离。

Boyer-Moore算法适用于长模式串，但实现相对复杂，此处不作详细展开。

五、总结

字符串匹配算法的选择取决于实际应用场景：

-朴素匹配：简单易实现，适用于小规模数据。

-KMP算法：通用性强，效率高，适合大规模文本处理。

-Boyer-Moore算法：速度最快，但实现复杂，适用于长模式串。

三、KMP算法（Knuth-Morris-Pratt）

KMP算法是对朴素匹配的优化，通过预处理模式串，避免主串指针的无效回退，从而将时间复杂度降低至O(n)。其核心在于利用模式串自身的特性，在发生不匹配时，尽可能多地跳过已经确认不会匹配的部分，从而提高匹配效率。KMP算法主要由两部分组成：部分匹配表的构建（Next数组的生成）和基于部分匹配表的匹配过程。

（一）核心思想与优势

KMP算法的核心思想是：当模式串与主串在某位置发生不匹配时，不需要将主串的指针回退到模式串指针之前的位置，而是利用已经计算出的模式串的部分匹配信息，将模式串向后滑动，使其在主串中的某个位置与之前匹配成功的部分对齐，从而继续比较。这种做法避免了主串指针的多次回退，显著提高了算法的效率。

KMP算法的优势主要体现在以下方面：

1.时间效率高：在最好和平均情况下，时间复杂度为O(n)，远优于朴素匹配的O(nm)。

2.空间复杂度可控：Next数组的构建需要额外的空间，但其空间复杂度为O(m)，其中m是模式串的长度。

3.通用性强：适用于多种字符串匹配场景，特别是当模式串较长或主串中存在大量重复子串时，性能优势更为明显。

（二）部分匹配表（Next数组）的构建

部分匹配表是KMP算法的关键，它记录了模式串的前缀和后缀的最长相同子串的长度。通过该表，可以在不匹配发生时，确定模式串应该滑动的位置。部分匹配表的构建过程如下：

1.初始化：

-创建一个与模式串等长的数组`Next`，用于存储部分匹配信息。

-初始化`Next[0]=-1`，因为单个字符的前缀和后缀不可能相同。

-设置指针`i`从1开始遍历模式串，`k`为当前`i`的前一个位置的最长相同子串长度（即`Next[k]`）。

2.遍历模式串，填充Next数组：

-对于每个位置`i`（从1到m-1），执行以下步骤：

(1)比较当前字符与前缀的最长相同子串的最后一个字符：

-若`pattern[i-1]==pattern[k]`，则说明当前前缀和后缀的最长相同子串长度加1，即`Next[i]=k+1`，然后`i++`和`k++`继续比较下一个字符。

-若不匹配，则需要更新`k`的值：将`k`设置为`Next[k-1]`，即回退到前一个最长相同子串的前一个位置，重复比较，直到`k==-1`或`pattern[i-1]==pattern[k]`。

(2)处理不匹配的情况：

-若`k==-1`，说明当前字符`pattern[i-1]`没有前缀和后缀相同的情况，因此`Next[i]=0`，然后`i++`继续遍历。

(3)更新Next数组：

-每次比较后，若找到匹配，则`Next[i]=k+1`；若未找到，则`Next[i]=0`（当`k==-1`时）。

3.Next数组的含义：

-`Next[i]`表示模式串`pattern[0...i-1]`中，最长相等的前缀和后缀的长度。

-例如，模式串`"ABCDABE"`的Next数组为`[-1,0,0,0,1,2,3]`，表示：

-`pattern[0]`："A"→无前缀和后缀相同，`Next[0]=-1`。

-`pattern[0...1]`："AB"→无相同子串，`Next[1]=0`。

-`pattern[0...3]`："ABCD"→无相同子串，`Next[3]=0`。

-`pattern[0...4]`："ABCDAB"→"AB"=="AB"，`Next[4]=1`。

-`pattern[0...5]`："ABCDABE"→"AB"=="AB"，`Next[5]=2`。

-`pattern[0...6]`："ABCDABE"→"ABCD"=="ABCD"，`Next[6]=3`。

（三）基于部分匹配表的匹配过程

在构建完Next数组后，即可开始匹配过程。匹配过程中，主串指针`i`和模式串指针`j`分别从0开始遍历，当字符匹配时，两者同时后移；当不匹配时，利用Next数组确定模式串的滑动位置。具体步骤如下：

1.初始化：

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

2.遍历主串和模式串：

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

(1)若相同：

-`i++`，`j++`，继续比较下一个字符。

-若`j==m`（模式串长度），则匹配成功，返回`i-j`（匹配起始位置）。

(2)若不同：

-若`j>0`，则将模式串指针`j`更新为`Next[j]`，即利用Next数组跳转。

-若`j==0`，说明当前匹配失败，仅移动主串指针`i++`，继续匹配下一个位置。

3.匹配失败：

-若遍历完主串仍未匹配成功（即`i==n`且未返回匹配位置），则返回-1表示不存在匹配。

4.示例：

-主串`text="ABCDABCDABE"`，模式串`pattern="ABCDABE"`，Next数组为`[-1,0,0,0,1,2,3]`。

-匹配过程：

-`i=0,j=0`，比较`'A'=='A'`，`i=1,j=1`。

-`i=2,j=2`，比较`'B'=='B'`，`i=3,j=3`。

-`i=4,j=4`，比较`'C'=='C'`，`i=5,j=5`。

-`i=6,j=6`，比较`'D'=='D'`，`i=7,j=7`。

-`i=8,j=8`，比较`'A'!='E'`，`j`更新为`Next[8]=3`（跳转至`'CDABE'`）。

-`i=8,j=3`，比较`'A'=='A'`，`i=9,j=4`。

-`i=10,j=5`，比较`'B'=='B'`，`i=11,j=6`。

-`i=12,j=7`，比较`'E'=='E'`，`j==m`，匹配成功，返回`i-j=5`。

（四）时间复杂度分析

1.Next数组的构建：

-遍历模式串一次，每次比较和更新Next数组的时间复杂度为O(1)，因此总时间复杂度为O(m)。

2.匹配过程：

-主串和模式串各遍历一次，每次比较和指针更新操作的时间复杂度为O(1)，因此总时间复杂度为O(n)。

3.总体时间复杂度：

-O(m)+O(n)=O(n+m)，即线性时间复杂度。

（五）空间复杂度分析

-Next数组占用O(m)的额外空间，因此KMP算法的空间复杂度为O(m)。

（六）适用场景

KMP算法适用于以下场景：

1.模式串较长：当模式串长度m较大时，KMP算法的效率优势明显。

2.主串中存在大量重复子串：KMP算法能够有效利用重复子串的信息，减少不必要的比较。

3.需要多次匹配同一模式串：Next数组的预处理可以在多次匹配时复用，提高效率。

四、Boyer-Moore算法简介

Boyer-Moore算法是另一种高效的字符串匹配算法，其核心思想是通过“坏字符规则”和“好后缀规则”跳过大量无效比较，时间复杂度可达O(n/m)。该算法在模式串较长时表现优异，但实现相对复杂，因此此处仅作简要介绍。

（一）坏字符规则（BadCharacterRule）

坏字符规则基于模式串中不匹配的字符，计算模式串可以滑动的最大距离。具体步骤如下：

1.坏字符表构建：

-创建一个坏字符表，记录模式串中每个字符最后出现的位置。若字符未出现，则记录为-1。

2.匹配过程中的坏字符处理：

-当主串和模式串在某位置不匹配时，找到模式串中与主串不匹配的字符（坏字符）。

-根据坏字符表，计算模式串可滑动的距离：

-