长度单位中并没有bm,BM算法被认为是亚线性串匹配算法,它在最坏情况下找到模式所有出现的时间复杂度为O(mn),在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
BM算法主要思想描述如下
(1)模式字符串的匹配顺序是从右向左:
(a)首先将P和T对齐,即p[0]和t[0]对齐;
(b)然后匹配从模式字符串P的最右端字符开始,即判断
p[m]和t[m]是否匹配:
如果匹配成功,则向左移动判断
p[m-1]和t[m-1]是否匹配,如此循环下去;如果匹配不成功,则进行字符串滑移。
(2)字符串滑移启发式策略:
(a)坏字符移动启发式策略
(b)好后缀移动启发式策略
两种策略的使用:如果同时满足两种策略使用条件时,选两者中较大的作为模式串向右滑移的距离。
温馨提示:答案为网友推荐,仅供参考