【安全课件】第17讲bm算法.pptx

BM算法是一种精确字符串匹配算法（区别于模糊匹配）。

BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

BM算法的基本流程: 设文本串T，模式串为P。

首先将T与P进行左对齐，然后进行从右向左比较，如下图所示:若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。

下面，来详细介绍一下坏字符规则和好后缀规则。

首先，诠释一下坏字符和好后缀的概念。

请看下图：图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。

1）坏字符规则（Bad Character）：在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：i. 如果字符x在模式P中没有出现，那么从字符x开始的m 个文本显然不可能与P匹配成功，直接全部跳过该区域即可。

ii. 如果x在模式P中出现，则以该字符进行对齐。

用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。

例1：下图红色部分，发生了一次不匹配。

计算移动距离Skip(c) = 5 - 3 = 2，则P向右移动2位。

移动后如下图：2）好后缀规则（Good Suffix）：若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。

ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。

用数学公式表示，设Shift(j)为P右移的距离，m为模式串P的长度，j 为当前所匹配的字符位置，s为t'与t的距离（以上情况i）或者x与P''的距离（以上情况ii）。

【字符串匹配】BM（Boyer-Moore）字符串匹配算法详解总结（附C++实现代码）BM算法思想的本质上就是在进⾏模式匹配的过程中，当模式串与主串的某个字符不匹配的时候，能够跳过⼀些肯定不会匹配的情况，将模式串往后多滑动⼏位。

BM算法寻找是否能多滑动⼏位的原则有两种，分别是坏字符规则和好后缀规则。

坏字符规则：我们从模式串的末尾往前倒着匹配，当我们发现某个字符⽆法匹配时，我们把这个⽆法匹配的字符叫做坏字符（主串中的字符）。

此时记录下坏字符在模式串中的位置si，然后拿坏字符在模式串中查找，如果模式串中并不存在这个字符，那么可以将模式串直接向后滑动m位，如果坏字符在模式串中存在，则记录下其位置xi，那么模式串向后移动的位数就是si-xi，（可以在确保si>xi，执⾏减法，不会出现向前移动的情况）。

如果坏字符在模式串中多次出现，那我们在计算xi的时候，选择最靠后的那个，这样不会因为让模式串滑动过多，导致本来可能匹配的情况被略过。

好后缀规则：在我们反向匹配模式串时，遇到不匹配时，记录下当前位置j位坏字符位置。

把已经匹配的字符串叫做好后缀，记作{u}。

我们拿它在模式串中查找，如果找到了另⼀个跟{u}相匹配的字串{u*}，那么我们就将模式串滑动到字串{u*}与主串{u}对齐的位置。

如下图所⽰：如果在模式串中找不到另⼀个等于{u}的⼦串，我们就直接将模式串滑动到主串中{u}的后⾯，因为之前的任何⼀次往后滑动，都没有匹配主串中{u}的情况。

但是这种滑动做法有点太过头了，可以看下⾯的例⼦，如果直接滑动到好后缀的后⾯，可能会错过模式串与主串可以匹配的情况。

如下图：当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重回部分相等的时候，就可能会存在完全匹配的情况。

所以针对这种情况我们不仅要看好后缀在模式串中，是否有另⼀个匹配的字串，我们还要考察好后缀的后缀字串是否存在跟模式串的前缀字串匹配的情况。

如下图所⽰：最后总结如何确定模式串向后滑动的位数，我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最⼤的。

bm算法分解多项式（原创实用版）目录1.引言2.BM 算法的原理3.BM 算法的步骤4.BM 算法的优点与应用5.总结正文1.引言在计算机科学中，多项式分解是一个重要的研究领域。

多项式分解指的是将一个多项式表达式分解为两个或两个以上的较简单的多项式之积。

近年来，随着计算机技术的快速发展，出现了许多用于分解多项式的算法，其中 BM 算法（Borwein-Moulton 算法）是一种非常高效且易于实现的分解方法。

本文将详细介绍 BM 算法的原理、步骤以及优点与应用。

2.BM 算法的原理BM 算法的原理基于以下两个重要定理：Vieta 定理和 Frobenius 定理。

Vieta 定理指出，如果一个多项式方程有根，那么它的系数与根之间存在一定的关系。

Frobenius 定理则表明，如果一个多项式可以被分解为两个多项式的乘积，那么这两个多项式的系数和根之间也存在一定的关系。

BM 算法正是利用这两个定理来实现多项式的高效分解。

3.BM 算法的步骤BM 算法的具体步骤如下：(1) 输入一个多项式 P(x)，首先将其转化为一个矩阵形式，记作 M。

(2) 对矩阵 M 进行初等行变换，将其化为阶梯形矩阵。

(3) 根据 Frobenius 定理，如果矩阵 M 的秩等于多项式 P(x) 的次数，那么 P(x) 可以被分解为两个多项式的乘积。

(4) 根据 Vieta 定理，求出分解后两个多项式的系数。

(5) 将求得的系数代入原式，得到分解后的多项式。

4.BM 算法的优点与应用BM 算法具有以下优点：(1) BM 算法的运行时间主要取决于矩阵的操作，而矩阵的操作是稳定的，因此 BM 算法具有很好的稳定性。

(2) BM 算法可以分解任意次数的多项式，且分解结果唯一。

(3) BM 算法易于实现，只需要进行简单的矩阵操作。

BM 算法在计算机科学中有广泛的应用，例如：在计算机图形学中，BM 算法可以用于计算多项式的根，从而实现图形的平滑；在密码学中，BM 算法可以用于分解大整数，从而提高加密算法的安全性。

BM算法一、概述字符串是一种线性表，在计算机科学领域，模式匹配问题一直都是学者们研究和关心的热点。

模式匹配时指在目标文本串检索子串的过程，其中字串成为模式。

模式匹配算法分为多模式匹配算法和单模式匹配算法，其中多模式匹配算法主要有AC算法及其他一些改进算法；单模式匹配算法主要有BF法、KMP法、BM算法及其一些改进算法（BMH算法和BMHS算法等）。

二、算法介绍1.常规的BF算法常规的BF算法在进行匹配时，移动模式串的方向时从左到右，而进行比较的时候也是从左到右，基本框架如下。

set j = 0;while( j <= ( strlen(主串) - strlen(模式串) ){For(i=0; i<strlen(模式串) && 模式串[i]==主串[j+i]; ++i);If(i==srlen(模式串))Return 结果;Else++j;}2.BM算法BM算法在移动模式串的时候是从左到右，而进行比较的时候是从右到左的，今本框架如下。

set j = 0;while( j <= ( strlen(主串) - strlen(模式串) ){For(i=stlen(模式串)-1; i>=0 && 模式串[i]==主串[j+i]; -- i);If(i<0)Return 结果;Else++j;}三、BM算法思想BM算法在进行字符串匹配的时候包含两个并行的算法，也就是所谓的bad-character shift，good-suffix shifit，即坏字符规则和好后缀规则，来决定字符不匹配时向后跳跃的距离。

下面来介绍这两个规则。

注：1.shilf就是模式串向后跳跃的距离2.x是模式串3.Y是目标串第一个规则：“bad-charact shift”(1)第一种情况很简单，就是在匹配的过程中，x中的a与y中的b没有匹配上，这时候判断b。

如果在x中没有发现b，就说明只要含有b的y的字串就不可能匹配成功，所以这时要直接跳到b的后面，继续匹配。

kmp算法bm算法
KMP算法和BM算法都是字符串匹配算法，用于在一个主串中查找特定的子串。

两者的不同点在于匹配失败时如何利用已匹配成功的信息进行下一次匹配。

KMP算法全称为Knuth-Morris-Pratt算法，是由Donald Knuth、James H. Morris和Vaughan Pratt于1977年联合发表的。

其核心思想是利用已经匹配成功的信息来消除无用的匹配。

具体实现中，KMP算法使用一个前缀函数数组F来记录每个子串的前缀中最长的既是该子串的真前缀又是该子串的真后缀的长度，若在匹配中出现了失配，则可利用前缀函数的信息进行跳转，以避免重复的匹配。

KMP算法在理论和实践中均有很高的效率和广泛的应用，例如在文本编辑器和编译器中常常使用KMP算法来实现查找和替换的功能。

BM算法全称为Boyer-Moore算法，是由Robert S. Boyer和J Strother Moore于1977年发明的另一个字符串匹配算法。

BM算法的核心思想是从模式串的末尾逐个比较主串中的字符，若出现不匹配的字符，则尽可能地利用模式串中已经匹配的字符的关系向后滑动模式串，以尽可能地跳过不符合条件的情况。

BM算法相对于KMP算法的优点是更适合处理大量字符集的情况，并且在某些情况下能够比KMP算法更快地匹配。

BM算法也被广泛地应用在文本搜索和文件压
缩等领域。

两种算法各有优劣，可以针对不同的应用场景选择不同的算法来实现字符串匹配。

在实际使用中，如果主串和模式串的长度都比较小，那么KMP算法相对来说比较简单实用，而如果主串或模式串的长度非常长或者字符集非常大，那么BM算法的效率可能更高，可以采用BM 算法来实现字符串匹配。

BM算法详解及Java实现1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。

该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。

在实践中，比KMP算法的实际效能高。

一、后缀暴力匹配算法后缀匹配，是指模式串的比较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀暴力匹配算法的改进。

所以还是先从最简单的后缀暴力匹配算法开始。

下面直接给出伪代码，注意这一行代码：j++；BM算法所做的唯一的事情就是改进了这行代码，即模式串不是每次移动一步，而是根据已经匹配的后缀信息，从而移动更多的距离。

/*** 后缀暴力匹配** @param T 正文字符数组* @param P 模式字符数组* @return匹配位置*/public static int bf(char[] T, char[] P) {for (int j = 0; j <= T.length - P.length; j++) {int i = P.length - 1;for (; i >= 0 && P[i] == T[i + j]; --i) {}if (i < 0) {return j;}}return -1;}二、BM算法介绍为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利用好后缀和坏字符可以大大加快模式串的移动距离，不是简单的++j，而是j+=max (shift(好后缀), shift(坏字符))。

下面举例说明BM算法。

例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

1. 首先，"文本串"与"模式串"头部对齐，从尾部开始比较。