字符串序列匹配算法优化

21/25字符串序列匹配算法优化第一部分哈希函数优化 2第二部分KMP算法优化 4第三部分后缀树算法优化 7第四部分Boyer-Moore算法优化 9第五部分Rabin-Karp算法优化 12第六部分滚动的哈希算法优化 14第七部分块搜索算法优化 18第八部分多模式匹配算法优化 21

第一部分哈希函数优化哈希函数优化

在字符串序列匹配算法中，哈希函数扮演着至关重要的角色，它将字符串映射成一个固定长度的哈希值，使字符串的比较可以通过哈希值来完成，从而大幅提高匹配效率。

优化哈希函数可以有效提升匹配算法的性能。本文将介绍几种常用的哈希函数优化技术：

1.多项式哈希

多项式哈希是一种基于模运算的哈希函数，其基本思想是将字符串中的字符视为一个多项式的系数，并对该多项式取模得到哈希值。

设字符集为Σ，字符串S=s[1],s[2],...,s[n]，则其多项式哈希值定义为：

```

hash(S)=(s[1]×p^(n-1)+s[2]×p^(n-2)+...+s[n])%mod

```

其中，p为一个质数，mod为一个较大的素数。

多项式哈希的优点在于，当S的后缀或前缀发生变化时，其哈希值可以通过线性时间更新，这使得它适用于滚动哈希等场景。

2.Rabin-Karp哈希

Rabin-Karp哈希是一种经典的哈希函数，其基本原理与多项式哈希类似，但采用了不同的取模方式。

设字符集为Σ，字符串S=s[1],s[2],...,s[n]，则其Rabin-Karp哈希值定义为：

```

hash(S)=((s[1]×q+s[2])×q+...+s[n])%mod

```

其中，q为一个固定常数，mod为一个较大的素数。

Rabin-Karp哈希的优势在于其哈希值计算简单高效，且在某些情况下可以证明其时间复杂度为O(n)。

3.循环移位哈希

循环移位哈希是一种专门针对循环字符串匹配场景设计的哈希函数。其基本思想是将循环字符串的所有循环移位视为一个整体来哈希。

设循环字符串S=s[1],s[2],...,s[n]，则其循环移位哈希值定义为：

```

hash(S)=hash(s[1],s[2],...,s[n])⊕hash(s[2],s[3],...,s[n],s[1])⊕...⊕hash(s[n],s[1],...,s[n-1])

```

其中，hash(·)为一个普通的哈希函数，⊕为异或运算。

循环移位哈希的优点在于，当循环字符串发生循环移位时，其哈希值保持不变，这使得它适用于循环字符串匹配算法。

4.随机哈希

随机哈希是一种哈希函数，其哈希值由多个随机生成的函数的组合得到。

设字符串S=s[1],s[2],...,s[n]，则其随机哈希值定义为：

```

hash(S)=(h1(S)^h2(S)^...^hk(S))%mod

```

其中，h1(·),h2(·),...,hk(·)为k个随机生成的哈希函数，mod为一个较大的素数。

随机哈希的优点在于其抗碰撞性较强，即对于不同的字符串，其哈希值碰撞的概率较低，这使得它适用于大规模字符串匹配场景。

以上介绍了四种常用的哈希函数优化技术。在实际应用中，根据不同的匹配场景和要求，可以选择最合适的哈希函数优化技术，以提升字符串序列匹配算法的性能和效率。第二部分KMP算法优化关键词关键要点【多项式预处理优化】

1.将模式串P转换为多项式P(x)，并预计算其幂次。

2.使用快速傅里叶变换(FFT)或分治傅里叶变换(DFT)来快速计算字符串串S和模式串P的多项式乘积。

3.时间复杂度从O(n^2)优化到O(nlogn)。

【后缀自动机优化】

KMP算法优化

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它在BM算法（Boyer-Moore算法）的基础上进行了改进。KMP算法通过利用部分匹配表（PMT）来跳过与模式串不匹配的文本串字符，从而提高匹配效率。

部分匹配表（PMT）

PMT是KMP算法的核心，它是一个包含模式串每个前缀最长后缀长度的数组。PMT的计算过程如下：

1.将PMT[0]初始化为0。

2.对于模式串中的每个字符：

-如果字符与PMT[i-1]指向的字符相等，则PMT[i]=PMT[i-1]+1。

-否则，PMT[i]=0。

KMP匹配算法

KMP匹配算法使用PMT来执行匹配过程，如下所示：

1.初始化两个指针：i（文本串指针）和j（模式串指针），两者都指向第一个字符。

2.如果文本串和模式串的当前字符匹配（text[i]==pattern[j]），则令i和j同时向后移动一位。

3.如果文本串和模式串的当前字符不匹配：

-如果j不等于0，则将j移动到PMT[j-1]指向的位置。

-否则，将i移动一位，重置j为0。

4.重复步骤2或3，直到模式串的末尾（j==m），或者文本串的末尾（i==n）。

优化

KMP算法的优化主要集中在PMT的计算上。以下是一些常见的优化技术：

Galil优化

Galil优化通过将模式串的逆序与PMT的逆序进行匹配来计算PMT。这种优化可以将PMT的计算时间复杂度从O(m)减少到O(1)，其中m是模式串的长度。

Morris-Pratt优化

Morris-Pratt优化利用模式串的字符重复性来改进PMT的计算。如果当前字符与PMT[j-1]指向的字符不匹配，则将j直接移动到PMT[PMT[j-1]]指向的位置。这种优化可以进一步降低PMT的计算时间复杂度。

Shift-Or优化

Shift-Or优化通过使用按位或运算来计算PMT。这种优化可以简化PMT的计算过程，并提高其效率。

应用

KMP算法及其优化技术广泛应用于字符串匹配场景，包括：

-文本搜索引擎

-语法分析器

-数据压缩

-生物信息学

优势

KMP算法具有以下优势：

-平均情况下的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度。

-在最坏情况下，时间复杂度为O(nm)，但这种情况很少出现。

-对预处理敏感，利用PMT可以显着提高匹配效率。

局限性

KMP算法也存在一定的局限性：

-预处理时间复杂度为O(m)，其中m是模式串的长度。

-仅适用于固定长度的模式串。第三部分后缀树算法优化关键词关键要点【后缀树算法优化】

1.使用单链表存储后缀树的节点，可以减少内存占用，提高查询效率。

2.采用分层构建法，将后缀树的构建过程分为多个阶段，每个阶段只处理一部分后缀，可以有效降低算法的时间复杂度。

3.引入后缀链接，可以快速获取后缀树中某个后缀的父后缀，提高算法的性能。

【后缀数组优化】

后缀树算法优化

简介

后缀树是一种用于字符串匹配的树形数据结构，它能高效地查找模式串在给定文本串中的所有出现位置。然而，随着文本串和模式串长度的增加，后缀树的构造和查询时间复杂度会迅速增加。因此，需要对后缀树算法进行优化以提高其效率。

优化策略

1.基于染色体的后缀树

传统的Ukkonen后缀树算法使用显式指针来连接树中的节点，这会带来大量的内存开销。染色体后缀树优化通过使用二进制编码来表示树中的路径，从而减少了内存消耗。

2.后缀链接

后缀链接是一种将节点与其子树的根节点相连的特殊指针。通过后缀链接，可以快速跳到一个模式串在后缀树中的下一个出现位置，从而减少了查询时间复杂度。

3.字符集优化

如果文本串的字符集较小，可以将树中的每个节点表示为一个位向量，其中每个位表示字符集中一个字符的存在与否。这种优化减少了节点的存储空间，提高了算法效率。

4.后缀数组

后缀数组是一种基于后缀树的压缩数据结构，它存储每个后缀在所有后缀之间的顺序。后缀数组提供了与后缀树类似的功能，但具有更小的内存需求和更快的构造时间。

5.稀疏后缀树

稀疏后缀树仅存储文本串频繁出现的子串，从而减少了树的大小和构造时间。然而，这可能会影响查询算法的效率。

6.启发式优化

启发式优化技术可以应用于后缀树算法以进一步提高其效率。例如，在构造后缀树时，可以只处理文本串中重复出现的子串，从而减少算法的运行时间。

应用

后缀树算法优化已广泛应用于各种领域，包括：

*生物信息学：基因组装配、序列比对

*自然语言处理：文本索引、模式识别

*数据挖掘：频繁模式挖掘、异常检测

*信息检索：快速全文搜索、相关文档检索

结语

后缀树算法优化是提高字符串匹配效率的关键技术。通过采用染色体表示、后缀链接、字符集优化、后缀数组、稀疏后缀树和启发式优化等策略，可以显著减少后缀树的构造和查询时间复杂度，使其适用于处理大规模文本数据。第四部分Boyer-Moore算法优化关键词关键要点BM算法的Horspool改进

1.采用失配字符表，记录模式串中每个字符的下一个出现位置，若不匹配则直接跳过该距离。

2.无需通过字符串比较判断失配位置，查找效率更高。

3.适用于模式串中字符重复较多的场景。

BM算法的双向查找

1.同时从模式串的头部和尾部开始匹配，提高匹配速度。

2.适用于模式串较长且包含大量重复字符的场景。

3.可以在匹配过程中动态调整搜索方向，提高匹配准确性。

BM算法的TurboBoyer-Moore

1.引入多模式模式的概念，将模式串划分成多个子串，同时进行匹配。

2.利用后缀树，快速获取子串的失配信息，加快匹配过程。

3.适用于大量模式串同时匹配的场景，提高总体匹配效率。

BM算法的FGK算法

1.基于有限自动机和广度优先遍历，以模式串中的第一个字符作为起点进行匹配。

2.构建失配自动机，记录失配转移状态，指导匹配过程。

3.适用于模式串中包含大量重复字符的场景，匹配速度快。

BM算法的Shift-Or算法

1.使用多位移位操作，代替字符串比较，实现快速失配检测。

2.降低了匹配过程中字符比较的次数，提高了匹配效率。

3.适用于模式串较短且字符重复较多的场景。

BM算法的Raita算法

1.引入滚动哈希技术，利用哈希函数快速计算子串哈希值进行匹配。

2.采用滑动窗口，动态更新子串哈希值，降低计算开销。

3.适用于模式串较长且包含大量重复字符的场景，匹配速度快。Boyer-Moore算法优化

简介

Boyer-Moore算法是一种字符串模式匹配算法，以其出色的平均查找速度而闻名。它通过两种主要优化来提高效率：字符预处理和坏字符规则。

字符预处理

字符预处理建立了一个字符查找表，称为坏字符表。该表指定了模式中的每个字符在模式末尾之前可以跳过的最大字符数。

对于字符c在模式中的位置i，坏字符表中的值是：

*模式长度，如果在模式中没有其他c

*模式中最后一个c和c在模式中的位置之间的差值

坏字符规则

坏字符规则指定，如果在文本中发现与模式中不匹配字符的情况，则模式应该向右移动一个与坏字符表中的值相等的距离。

优化技巧

除了坏字符规则外，还有其他技巧可以进一步优化Boyer-Moore算法：

好后缀规则

好后缀规则确定模式的尾部子串是否也在模式的前缀中出现。如果是，则模式向上移动一定距离以对齐模式中的“好后缀”和文本中的“好前缀”。

加利略优化

加利略优化采用双向扫描模式和文本，以减少比较次数。模式从右到左扫描，文本从左到右扫描。

霍尔森优化

霍尔森优化通过以下方式进一步改进加利略优化：

*在文本扫描期间，跳过已知不会产生匹配的字符。

*仅扫描文本中的子串，这些子串包含模式的至少一个字符。

非平凡优化

非平凡优化包括：

*批量比较：同一列中同时比较多个文本字符。

*多模式匹配：一次搜索多个模式。

*并行化：利用多核处理器同时进行多个匹配。

应用

Boyer-Moore算法优化及其变体广泛用于各种应用中，包括：

*文本编辑和处理

*搜索引擎和信息检索

*生物信息学和基因组学

*数据挖掘和模式识别

总的来说，Boyer-Moore算法优化提供了一种高效且可靠的字符串模式匹配解决方案。通过利用字符预处理、坏字符规则和其他优化技巧，它可以显着提高查找速度，使之成为各种应用程序的首选选择。第五部分Rabin-Karp算法优化关键词关键要点哈希函数选择优化

-

-针对不同字符串序列特征选择高效的哈希函数，如滚动哈希、失配树等。

-利用布隆过滤器减少哈希冲突，提高算法效率。

-采用分块哈希技术，将长字符串划分为较小的块，分别计算哈希值，降低计算复杂度。

文本预处理优化

-拉宾-卡普算法优化

拉宾-卡普算法是一种字符串序列匹配算法，它使用哈希函数来快速比较字符串子串和模式串。为了提高算法的效率，已开发了以下优化技术：

滚动哈希

滚动哈希技术通过在滑动窗口中移动时重新计算哈希值，避免了每次比较子串时重新计算哈希值。这可以通过使用下列等式实现：

```

哈希(滑动窗口)=(哈希(前一个滑动窗口)-(模式串长度*哈希(丢弃的字符)))*基数+哈希(新字符)

```

预处理模式串

通过预处理模式串，可以快速计算每个模式串字符位置的哈希值。在实际应用中，可以使用一个长度为模式串长度的数组，存储每个模式串字符的哈希值。

快速模运算

在滚动哈希过程中需要进行大量的模运算。为了提高效率，可以使用位掩码技术或快速模运算算法进行优化。

改进的哈希函数

为了减少哈希冲突并提高准确性，可以使用改进的哈希函数，例如：

*Rabin-Karp指纹

*Jenkins哈希

*xxHash

使用多项式哈希

多项式哈希使用多项式来计算哈希值。这可以减少哈希冲突并提高算法的鲁棒性。

利用SIMD指令

在现代计算机体系结构中，可以利用单指令多数据(SIMD)指令来并行计算哈希值。这可以显著提高算法在多核处理器上的效率。

其他优化技术

此外，还有以下其他优化技术可以提高拉宾-卡普算法的效率：

*使用跳过表减少模式串匹配次数

*使用布隆过滤器排除不匹配的候选子串

*使用启发式方法以特定顺序比较模式串和子串的字符

通过应用这些优化技术，拉宾-卡普算法可以显著提高字符串序列匹配的效率，特别是在大规模文本数据处理中。第六部分滚动的哈希算法优化关键词关键要点滚动哈希函数

1.滚动哈希函数是一种用于快速计算字符串哈希值的技术，它通过将字符串窗口中的字符逐个添加和删除来更新哈希值。

2.滚动哈希函数的时间复杂度为O(n)，其中n为字符串的长度，比重新计算哈希值更加高效。

3.滚动哈希函数可以用于快速查找字符串中的子串，通过比较哈希值来确定子串是否匹配。

循环平移

1.循环平移是指将字符串中的字符向左或向右平移一定位数，得到一个新的字符串。

2.滚动哈希函数可以应用于循环平移，通过使用循环平移窗口来计算每个循环平移的哈希值。

3.循环平移哈希函数可以快速查找字符串中的所有循环平移，并用于模式匹配和重复检测。

多项式哈希

1.多项式哈希是一种使用多项式模运算来计算哈希值的技术，它具有更好的抗碰撞能力。

2.多项式哈希函数可以提高哈希碰撞的概率，确保不同字符串具有不同的哈希值。

3.多项式哈希函数的时间复杂度为O(nlogn)，与使用质数模运算的哈希函数相比，它具有更好的精度。

基于字长的哈希

1.基于字长的哈希是将字符串划分为更小的子字符串并分别计算哈希值的技术，它提高了哈希计算效率。

2.基于字长的哈希函数的时间复杂度为O(n/w)，其中w为子字符串长度，比逐个字符计算哈希值更快。

3.基于字长的哈希函数适用于大字符串的哈希计算，并用于快速文本索引和模式匹配。

并发哈希

1.并发哈希是指使用多线程同时计算哈希值的技术，它提高了哈希计算的吞吐量。

2.并发哈希函数通过将字符串划分为多个块并在不同的线程上计算哈希值来实现并行计算。

3.并发哈希函数适用于大数据的哈希计算，减少了哈希计算时间，提高了整体效率。

自适应哈希

1.自适应哈希是指根据输入数据自动调整哈希函数的技术，它提高了哈希计算的精度。

2.自适应哈希函数使用机器学习或其他算法来分析输入数据并优化哈希函数的参数。

3.自适应哈希函数适用于处理不同类型的字符串数据，改善了哈希碰撞的概率，增强了哈希计算的可靠性。滚动的哈希算法优化

简介

滚动的哈希算法是一种字符串序列匹配算法优化技术，它通过减少重新计算哈希值的数量来提高性能。该技术适用于存在大量重叠的字符串比较场景。

基本原理

滾動哈希算法利用哈希函数对字符串窗口进行哈希计算。当窗口移动时，新窗口的哈希值可以通过利用前一个窗口的哈希值和新进入的字符来快速计算，而不是从头开始重新计算。

算法步骤

1.计算目标字符串的初始窗口哈希值。

2.循环遍历模式字符串，逐步扩大或缩小窗口：

-如果窗口长度小于模式字符串，则将下一个字符添加到窗口中。

-如果窗口长度大于或等于模式字符串，则将窗口左侧的第一个字符删除。

3.利用前一个窗口的哈希值和新进入或移出的字符，计算新窗口的哈希值。

4.比较新窗口的哈希值与模式字符串的哈希值。如果相等，则检查这两个窗口是否字符匹配，从而判断匹配成功。

优化效果

与朴素的字符串比较算法相比，滚动的哈希算法可以显著提高性能：

-减少哈希计算:由于仅需要重新计算与窗口大小相等的哈希值，因此大大减少了哈希计算的次数。

-快速窗口更新:利用前一个窗口的哈希值快速计算新窗口的哈希值，避免了从头开始重新计算。

-适用性广:滚动的哈希算法适用于存在大量重叠的字符串比较场景，如文本搜索、模式匹配、数据挖掘等。

应用

滾動哈希算法广泛应用于以下领域：

-文本搜索:在文本中快速找到匹配特定模式的所有子字符串。

-模式匹配:在数据集或文本流中高效识别特定模式的出现。

-数据挖掘:从大量数据集中提取有意义的模式或关联。

-网络安全:识别恶意软件、检测入侵行为。

示例

考虑以下示例：

目标字符串：`ABACABAD`

模式字符串：`AB`

步骤：

1.计算初始窗口`AB`的哈希值。

2.逐步扩大窗口：

-`ABC`哈希值=`AB`哈希值+`C`哈希值-`A`哈希值

-`ABCD`哈希值=`ABC`哈希值+`D`哈希值-`B`哈希值

3.比较窗口哈希值与模式字符串哈希值：

-`ABC`哈希值与`AB`哈希值相等，匹配成功。

-`ABCD`哈希值与`AB`哈希值不等，继续扩大窗口。

结论

滚动的哈希算法优化是一种高效的字符串序列匹配技术，通过减少重新计算哈希值的数量和快速更新窗口，显著提高了性能。其广泛应用于文本搜索、模式匹配、数据挖掘和网络安全等领域。第七部分块搜索算法优化关键词关键要点哈希函数优化

-KMP算法优化：采用哈希函数对模式串进行预处理，快速定位匹配位置，减少比较次数。

-Rabin-Karp算法优化：使用滚动哈希技术，通过一次哈希计算比较模式串和文本串的部分，提高匹配效率。

-布隆过滤器优化：利用布隆过滤器快速排除不匹配的文本段，减少无效搜索，提升匹配速度。

模式串预处理优化

-预处理算法优化：对模式串进行预处理，生成匹配信息表或状态机，减少匹配过程中对文本串的访问次数。

-并行化模式串预处理：将模式串预处理过程并行化，利用多核处理器提升预处理效率，缩短匹配时间。

-预处理算法改进：研究高效的模式串预处理算法，降低算法复杂度，提高预处理性能。

文本串分块优化

-文本串分块：将文本串划分为多个子块，分别进行匹配，减少一次匹配需要处理的文本量。

-分块大小优化：根据文本串和模式串的特性，确定最优的分块大小，平衡匹配效率和算法复杂度。

-并行化文本串分块匹配：将文本串分块匹配过程并行化，利用多核处理器提升匹配效率，缩短匹配时间。

启发式搜索优化

-启发式匹配策略：基于启发式规则或特征，快速定位潜在的匹配位置，减少无意义的搜索。

-基于模式串相似度的启发式：根据模式串和文本串的相似度，优先搜索相似度更高的文本区域。

-基于文本串结构的启发式：利用文本串的特殊结构，如分词或语法特征，指导匹配过程，提高匹配效率。

多模式匹配优化

-多模式串索引：建立多模式串索引，快速查找匹配多个模式串的文本位置。

-并行化多模式串匹配：将多模式串匹配过程并行化，利用多核处理器提升匹配效率，缩短匹配时间。

-多模式串匹配算法改进：研究高效的多模式串匹配算法，降低算法复杂度，提高匹配性能。

其他优化技术

-基于GPU的匹配加速：利用GPU的并行计算能力，加快匹配过程，提升匹配效率。

-基于云计算的匹配优化：将匹配过程部署到云端，利用分布式计算资源提升匹配规模和效率。

-基于机器学习的匹配优化：利用机器学习算法，训练匹配模型，提升匹配准确性和效率。块搜索算法优化

简介

块搜索算法是字符串序列匹配算法的一种，它将待匹配字符串划分为大小相等的块，并使用一个哈希函数对每个块进行哈希计算。然后，它将哈希值与目标字符串中的哈希值进行比较，以确定是否存在匹配。如果哈希值匹配，则进一步执行字符比较以确认匹配。

优化策略

1.哈希函数优化：

*选择一个碰撞率低的哈希函数，如MurmurHash或xxHash。

*使用多重哈希函数，即为每个块应用不同的哈希函数，以减少碰撞。

2.块大小优化：

*选择一个合适的块大小。块大小太小会导致过多的散列计算，而块大小太大则会降低匹配效率。

*实验确定最佳块大小，通常在32到64字节之间。

3.预处理优化：

*预处理目标字符串，为每个块计算哈希值并存储在哈希表中。这可以加快哈希值的比较速度。

*对于较长的目标字符串，可以将预处理结果分段存储，以减少内存占用。

4.滚动哈希优化：

*使用滚动哈希算法，而不是为每个块重新计算哈希值。这可以减少哈希计算开销，并提高匹配速度。

*滚动哈希算法通过在当前哈希值的基础上计算后续块的哈希值，从而避免对每个块进行单独计算。

5.多核优化：

*使用多核处理器并行执行哈希计算和匹配检查。这可以显著提高匹配速度，特别是对于大规模字符串比较任务。

*可以使用OpenMP或其他并行编程库来实现多核优化。

6.lookahead优化：

*使用lookahead缓冲区来存储目标字符串的未来块。这允许算法在比较当前块时提前计算后续块的哈希值。

*lookahead缓冲区的大小应经过实验确定，以平衡减少比较开销和增加内存占用之间的权衡。

7.位图优化：

*使用位图来存储预处理的目标字符串的已知字符。这可以快速排除没有匹配可能的字符，从而减少字符比较的开销。

*位图优化特别适用于目标字符串中字符集较小的情况。

性能提升

通过实施这些优化，块搜索算法的性能可以显着提高，尤其是在处理大规模字符串比较任务时。优化后的算法可以比未优化的算法快几个数量级。

其他改进

*使用跳跃表或查找树来组织预处理的哈希值，以提高查找效率。

*使用伽罗瓦域（GF）乘法来替代哈希计算，以进一步减少计算开销。

*探索人工智能技术，如神经网络，来设计更有效的块搜索算法。

这些额外的改进可以进一步提升块搜索算法的性能和可扩展性。第八部分多模式匹配算法优化多模式匹配算法优化

多模式匹配算法旨在在给定的目标序列中查找多个模式的匹配项。为了提高这些算法的效率，已经提出了多种优化策略：

1.AC自动机(Aho-Corasick)

AC自动机是一种有限状态自动机，它建立在Trie树之上，用于高效匹配多个模式。它使用以下策略：

*状态转移表：为每个状态构建一个状态转移表，指示在给定字符输入时应转移到的状态。

*失效函数：为每个状态计算一个失效函数，它定义了在不匹配字符后应返回的状态。

*输出函数：为每个状态关联一个输出函数，该函数在匹配模式时产生输出。

2.后缀树

后缀树是一种紧凑的数据结构，它存储字符串的所有后缀。它支持以下优化：

*共享后缀：后缀树可以利用字符串中的重复后缀，避免为每个模式重复存储信息。

*快速匹配：通过沿着后缀树遍历，可以快速查找模式匹配项，因为每个节点代表一个共同后缀。

3.KMP算法(Knuth-Morris-Pratt)

KMP算法是一种高效的单模式匹配算法，它使用以下优化：

*前缀函数：为模式计算一个前缀函数，它指示在部分匹配失败后应跳转到的位置。

*快速失败：当字符不匹配时，算法使用前缀函数快速跳转到模式中的下一个候选匹配项。

4.BM算法(Boyer-Moore)

BM算法是一种多模式匹配算法，它使