bm是什么意思？

BM是一种匹配算法。
BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
BM算法主要思想描述如下：
模式字符串的匹配顺序是从右向左:
1、首先将P和T对齐，即p和t对齐；
2、然后匹配从模式字符串P的最右端字符开始，即判断p[m]和t[m]是否匹配：
如果匹配成功，则向左移动判断p[m-1]和t[m-1]是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。
BM算法的原理：
不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理 P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。
这样，就需要将字串中的所有字符一一比较。Boyer-Moore算法的关键在于，当 P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。
如果最后一个字符未在 P中出现，那么我们可以直接跳过 T的n个字符，比较接下来的n个字符，n为 P的长度（见定义）。
如果最后一个字符出现在 P中，那么跳过的字符数需要进行计算（也就是将 P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。

文章标签：

来自：bm什么意思

本文链接：https://www.u1e.cn/baike/a/45063b795ca6a52c5cbcdb30 [复制]