字符串算法-BMH

时间:2023-01-06 22:12:49

BMH算法全称是Boyer-Moore-Horspool算法。它不再像BM算法一样关注失配的字符,它的关注的焦点在于匹配文本每一次匹配失败的最后一个字符X,根据这个字符X是否在模板出现过来决定跳跃的步数,否则跳跃模板的长度。

字符串算法-BMH

所以分了两种情况:

一:字符X不在模板P中,则跳跃的步数为模板P的长度

二:字符X在模板P中,跳跃的步数为字符X距离离尾部最近的字符X的距离(不包括最后一个字符)

字符串算法-BMH

加入文本为missipipi,模板为pip:

字符串算法-BMH

只要三次匹配即可。