BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。

本页面主要目录有关于BM的：概括介绍等介绍

外文名

bm

含义

一种精确字符串匹配算法

应用领域

Boyer-Moore

概括介绍

BM算法主要思想描述如下

(1)模式字符串的匹配顺序是从右向左:

(a)首先将P和T对齐，即p和t对齐；

(b)然后匹配从模式字符串P的最右端字符开始，即判断

p[m]和t[m]是否匹配：

如果匹配成功，则向左移动判断

p[m-1]和t[m-1]是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。

(2)字符串滑移启发式策略：

(a)坏字符移动启发式策略

(b)好后缀移动启发式策略

两种策略的使用：如果同时满足两种策略使用条件时，选两者中较大的作为模式串向右滑移的距离。