bm坏字符 , Horspool算法 以及Sunday算法的不同

时间:2021-11-05 10:52:31

bm坏字符 , Horspool算法 以及Sunday算法的不同

一.bm中的坏字符规则思想

(1)模式串与主串从后向前匹配

(2)发现坏字符后,如果坏字符不存在于模式串中:将模式串的头字符与坏字符后一位对齐

(3) 发现坏字符后,如果坏字符不存在于模式串中:将模式串中坏字符最后一次出现的位置与坏字符对齐

bm坏字符 , Horspool算法 以及Sunday算法的不同

二. Horspool算法思想

在Horspool算法中有一个关注字符,当出现不匹配的时候根据关注字符的情况对模式串进行移动

(1)关注字符为模式串最后一个字符与主串对应的字符,模式串与主串从后向前匹配

(2)当出现坏字符时,若关注字符不存在于模式串中: 将模式串的头字符与关注字符后一位对齐

(3) 当出现坏字符时,若关注字符存在于模式串中: 将模式串中关注字符最后一次出现的位置与坏字符对齐

bm坏字符 , Horspool算法 以及Sunday算法的不同

三.Sunday算法思想

Sunday算法与Horspool算法思想极为相像,总的来说有两点不同

(1) 模式串与主串从前向后匹配

(2) 关注字符为模式串最后一个字符与主串对应的字符的后一个字符

bm坏字符 , Horspool算法 以及Sunday算法的不同