BF 算法性能会退化的比较严重,而 RK 算法需要用到哈希算法,而设计一个可以应对各种类型字符的哈 希算法并不简单。
BM(Boyer-Moore)算法。它是一种非常高效的字符串匹配算法,滑动算法
在这个例子里,主串中的 c,在模式串中是不存在的,所以,模式串向后滑动的时候,只要 c 与模式串 有重合,肯定无法匹配。所以,我们可以一次性把模式串往后多滑动几位,把模式串移动到 c 的后面。
BM 算法,本质上其实就是在寻找这种规律。借助这种规律,在模式串与主串匹配的过程中,当模式串 和主串某个字符不匹配的时候,能够跳过一些肯定不会匹配的情况,将模式串往后多滑动几位。
BM 算法包含两部分,分别是坏字符规则(bad character rule)和好后缀规则(good suffix shift)。
1、坏字符规则
BM 算法的匹配顺序比较特别,它是按照模式串下标从大到小的顺序,倒着匹配的。
我们从模式串的末尾往前倒着匹配,当我们发现某个字符没法匹配的时候。我们把这个没有匹配的 字符叫作坏字符(主串中的字符)。
字符 c 与模式串中的任何字符都不可能匹配。这个时候,我们可以将模式串直接往后滑动三位,将模式 串滑动到 c 后面的位置,再从模式串的末尾字符开始比较。
当发生不匹配的时候,我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在, 我们把这个坏字符在模式串中的下标记作 xi。如果不存在,我们把 xi 记作 -1。那模式串往后移动的位 数就等于 si - xi。(下标,都是字符在模式串的下标)
第一次移动3位
c在模式串中不存在xi = -1,所以 ,移动位数 n = 2- (-1) = 3
第一次移动2位
a在模式串中存在xi = 0,所以 ,移动位数 n = 2 - 0 = 2
2、好后缀规则
我们把已经匹配的 我们拿它在模式串中查找,如果找到了另一个跟{u}相匹配的子串{u},那我们就 将模式串滑动到子串{u}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于{u}的子串,我们就直接将模式串,滑动到主串中{u}的后面,因 为之前的任何一次往后滑动,都没有匹配主串中{u}的情况。
过度滑动情况:
当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候,并且重合的部分相等的时候,就有可能会 存在完全匹配的情况。
所以,针对这种情况,我们不仅要看好后缀在模式串中,是否有另一个匹配的子串,我们还要考察好后 缀的后缀子串(c),是否存在跟模式串的前缀子串(c)匹配的。
3、如何选择坏字符和好后缀
我们可以分别计算好后缀和坏字符往后滑动的位数,然后取两个数中最大的,作为模式串往后滑动的位 数。
坏字符:
如果我们拿坏字符,在模式串中顺序遍历查找,这样就会比较低效。
可以采用散列表,我们可以用一个256数组,来记录每个字符在模式串中的位置,数组下标可以直接对应字符的ASCII码值,数组的值为字符在模式串中的位置,没有的记为-1。
bc[97]=a
bc[98]=b
bc[100]=d
有重复的字母以后面的位置为准。
package graph;
/**
* * 滑动匹配算法--坏字符
*/
public class BMalth {
private static final int SIZE = 256; // 全局变量或成员变量
/**
* @param b
* @param m
* @param dc
*/
private static void generateBC(char[] b, int m, int[] dc) {
for (int i = 0; i < SIZE; ++i) {
dc[i] = -1; // 初始化 bc 模式串中没有的字符值都是-1
}
//将模式串中的字符希写入到字典中
for (int i = 0; i < m; ++i) {
int ascii = (int) b[i]; // 计算 b[i] 的 ASCII 值
dc[ascii] = i;
}
}
/**
* 坏字符
*
* @param a 主串
* @param b 模式串
* @return
*/
public static int bad(char[] a, char[] b) {
//主串长度
int n = a.length;
//模式串长度
int m = b.length;
//创建字典
int[] bc = new int[SIZE];
// 构建坏字符哈希表,记录模式串中每个字符最后出现的位置
generateBC(b, m, bc);
// i表示主串与模式串对齐的第一个字符
int i = 0;
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
//i+j : 不匹配的位置
if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是j
}
if (j < 0) {
return i; // 匹配成功,返回主串与模式串第一个匹配的字符的位置
}
// 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
// j:si bc[(int)a[i+j]]:xi
i = i + (j - bc[(int) a[i + j]]);
}
return -1;
}
public static void main(String[] args) {
String s1 = "abcabcabc";
String s2 = "cab";
System.out.println(bad(s1.toCharArray(), s2.toCharArray()));
}
}
BM算法的时间复杂度是O(N/M)
n:主串长度 m:模式串长度
BM算法比较高效,在实际开发中,特别是一些文本编辑器中,用于实现查找字符串功能。
页面更新:2024-04-21
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号