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

AC算法BM算法AC算法（Aho-Corasick Algorithm）AC算法是一种字符串算法，通常用于在一段文本中查询多个模式串的出现情况。

它是由Alfred V. Aho和Margaret J. Corasick于1975年提出的，并以他们的名字命名。

AC算法的原理是构建一个有限状态机（FSM），该状态机能够同时处理多个模式串的匹配。

该算法具有高效的时间和空间复杂度，并且能够在一次扫描内找到所有模式串的匹配位置。

下面将介绍AC算法的详细步骤：1. 构建Trie树（前缀树）：根据给定的模式串集合，构建一个Trie树。

Trie树是一种特殊的字典树，它能够实现快速的字符串匹配。

Trie树的根节点为一个空节点，每个节点都有多个子节点，每个子节点都代表一个字符。

从根节点到叶子节点的路径上的所有字符组成一个模式串。

2. 构建失败指针（Fail Pointer）：在Trie树中，每个节点的失败指针指向它的最长后缀节点，该后缀节点也是Trie树的节点。

如果一个节点的当前字符在其最长后缀节点的子节点中不存在，则将失败指针指向最长后缀节点的失败指针指向的节点。

如果没有最长后缀节点，则将失败指针指向根节点。

3. 在文本中匹配模式串：从文本的第一个字符开始，按照Trie树的路径进行匹配。

如果在一些节点匹配失败，则通过失败指针转移到下一个节点进行匹配，直到匹配成功或到达文本的末尾。

当匹配成功时，可以通过沿着失败指针回溯，找到其他可能的匹配位置。

4.输出匹配结果：对于每个文本字符，记录匹配的模式串。

使用一个结果链表，其中每个节点包括一个指向匹配的模式串的指针和该模式串在文本中的位置。

AC算法的时间复杂度为O(n+m)，其中n是文本的长度，m是模式串的总长度。

空间复杂度为O(m)，即模式串的长度。

BM算法（Boyer-Moore Algorithm）BM算法是一种字符串和匹配算法，通过对模式串的后缀进行预处理，实现在文本中的快速。

BM算法详解BM算法 后缀匹配，是指模式串的⽐较从右到左，模式串的移动也是从左到右的匹配过程，经典的BM算法其实是对后缀蛮⼒匹配算法的改进。

为了实现更快移动模式串，BM算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。

利⽤好后缀和坏字符可以⼤⼤加快模式串的移动距离，不是简单的++j，⽽是j+=max (shift(好后缀), shift(坏字符)) 先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下⼀个字符，继续⽐较，如下图：坏字符出现在模式串中，这时可以把模式串第⼀个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图： 此处配的图是不准确的，因为显然加粗的那个b并不是”最靠右的”b。

⽽且也与下⾯给出的代码冲突！我看了论⽂，论⽂的意思是最右边的。

当然了，尽管⼀时⼤意图配错了，论述还是没有问题的，我们可以把图改正⼀下，把圈圈中的b改为字母f就好了。

接下来的图就不再更改了，⼤家⼼⾥有数就好。

为了⽤代码来描述上述的两种情况，设计⼀个数组bmBc['k']，表⽰坏字符‘k’在模式串中出现的位置距离模式串末尾的最⼤长度，那么当遇到坏字符的时候，模式串可以移动距离为： shift(坏字符) = bmBc[T[i]]-（m-1-i)。

如下图： 数组bmBc的创建⾮常简单，直接贴出代码如下：1 void preBmBc(char *x, int m, int bmBc[]) {23 int i;45 for (i = 0; i < ASIZE; ++i)67 bmBc[i] = m;89 for (i = 0; i <= m - 1; ++i)1011 bmBc[x[i]] = m - i - 1;1213 } 代码分析：ASIZE是指字符种类个数，为了⽅便起见，就直接把ASCII表中的256个字符全表⽰了，哈哈，这样就不会漏掉哪个字符了。

【学习⼩记】Berlekamp-Massey算法PrefaceBM算法是⽤来求⼀个数列的最短线性递推式的。

形式化的，BM算法能够对于长度为n的有穷数列或者已知其满⾜线性递推的⽆穷数列a，找到最短的长度为m的有穷数列c，满⾜对于所有的i≥n，有a i=m∑j=1c j a i−jTextBM算法的流程⼗分简洁明了——增量，构造，修正。

⽅便起见，我们令a的下标从0开始，c的下标从1开始假设我们当前构造出来的递推系数C是第cnt版（经过cnt次修正）长度为m，能够满⾜前a0...a i−1项，记做cnt C，初始时cnt C为空,m=0记d i=a i−m∑j=1c j a i−j若d i=0，那么C符合的很好，不⽤管它否则，我们需要进⾏⼀定的修正，cnt C需要变换到cnt+1C。

记fail cnt表⽰cnt C在a i处拟合失败。

若cnt=0，说明这是a的第⼀个⾮0元素，直接设m=i+1,在C中填上i+1个0。

显然这满⾜定义式（因为前m项是可以不满⾜递推式的）。

否则我们考虑如何构造，如果能找到⼀个C′，满⾜对于m≤j≤i−1，都有m∑k=1c′k a j−k=0，且m∑k=1c′k a i−k=1那么可以构造cnt+1C=cnt C+d i C′，显然这⼀定满⾜性质。

其中加法为按项数对应加。

如何构造呢？我们可以利⽤之前的C！找到某⼀个k∈[t−1]我们构造设w=d id failk，构造wC′={0,0,0,0,...,0,w,−w∗k C}其中前⾯填上了i−fail k−1个0，后⾯相当于是k C乘上−w接在了后⾯。

为什么这是对的？其实很简单，对于a i，带进去的算出来的东西相当于是$$w a_{fail_k}-w(a_{fail_k}-d_{fail_k})=w d_{fail_k}=d_i$$⽽对于m≤j≤i−1，算出来的是正好是w∗a j−(i−failk)−w∗a j−(i−fail k)=0，利⽤了k C在1到fail k−1都满⾜关系式，⽽在fail k相差d的性质。

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 算法可以用于分解大整数，从而提高加密算法的安全性。