BM算法简单理解
什么是BM算法
BM算法算是RK（模式串与主串按位比较，主串按位后移）算法的变种，提高了移动的范围。达到优化的目的
BM算法的两大核心：坏字符&好后缀的处理。
坏字符
从***高->低***按位比较时的第一个不匹配的字符。
移动位数计算：mi = s i - xi
解析
- mi：主串比较向后移动位数
- si：坏字符对应的模式串下标
- xi：坏字符首次比对成功的模式串下标（初始值-1）
场景一：无一匹配
场景二：存在匹配
好后缀
说明模式串后缀存在部分匹配，那么针对这些部分匹配的内容需要进行优化滑动，如果匹配串再模式串中没有匹配的就可以整体跳过。
解析
一、后缀在模式串没有匹配的，那么可以直接移动到后缀之后
二、整个后缀再模式串中存在匹配，那么可以后缀对齐
三、部分后缀与模式串前缀部分匹配则需要前缀部分对齐了
完整代码
public class BMStringOther {
private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化 bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int) b[i]; // 计算 b[i] 的 ASCII 值
bc[ascii] = i;
}
}
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int i = 0; // i 表示主串与模式串对齐的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
// 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位
// 想想为什么这里可以？
// 首先这里从BC中拿到的就是匹配模式串中最近的下标。【所有模式串hash化是可以从后->前覆盖的】
i = i + (j - bc[(int) a[i + j]]);
}
return -1;
}
// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { // 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0, i]
int j = i;
int k = 0; // 公共后缀子串长度
while (j >= 0 && b[j] == b[m - 1 - k]) { // 与 b[0, m-1] 求公共后缀子串
--j;
++k;
suffix[k] = j + 1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
}
if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
}
}
// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm2(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j 表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
/*坏字符移动step*/
int x = j - bc[(int) a[i + j]];
int y = 0;
if (j < m - 1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] + 1;
for (int r = j + 2; r <= m - 1; ++r) {
if (prefix[m - r] == true) {
return r;
}
}
return m;
}
private static String logTemplate = "主串:[%s],模式串:[%s],起始位置:%s";
public static void main(String[] args) {
String mainStr = "aaaafds";
String compStr = "aaf";
System.out.println(String.format(logTemplate, mainStr, compStr, new BMStringOther().bm(mainStr.toCharArray(), mainStr.length(), compStr.toCharArray(), compStr.length())));
System.out.println(String.format(logTemplate, mainStr, compStr, new BMStringOther().bm2(mainStr.toCharArray(), mainStr.length(), compStr.toCharArray(), compStr.length())));
}
}public class BMStringOther {
private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化 bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int) b[i]; // 计算 b[i] 的 ASCII 值
bc[ascii] = i;
}
}
public int bm(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int i = 0; // i 表示主串与模式串对齐的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
// 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位
// 想想为什么这里可以？
// 首先这里从BC中拿到的就是匹配模式串中最近的下标。【所有模式串hash化是可以从后->前覆盖的】
i = i + (j - bc[(int) a[i + j]]);
}
return -1;
}
// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好了
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { // 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0, i]
int j = i;
int k = 0; // 公共后缀子串长度
while (j >= 0 && b[j] == b[m - 1 - k]) { // 与 b[0, m-1] 求公共后缀子串
--j;
++k;
suffix[k] = j + 1; //j+1 表示公共后缀子串在 b[0, i] 中的起始下标
}
if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
}
}
// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm2(char[] a, int n, char[] b, int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j 表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是 j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
/*坏字符移动step*/
int x = j - bc[(int) a[i + j]];
int y = 0;
if (j < m - 1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] + 1;
for (int r = j + 2; r <= m - 1; ++r) {
if (prefix[m - r] == true) {
return r;
}
}
return m;
}
private static String logTemplate = "主串:[%s],模式串:[%s],起始位置:%s";
public static void main(String[] args) {
String mainStr = "aaaafds";
String compStr = "aaf";
System.out.println(String.format(logTemplate, mainStr, compStr, new BMStringOther().bm(mainStr.toCharArray(), mainStr.length(), compStr.toCharArray(), compStr.length())));
System.out.println(String.format(logTemplate, mainStr, compStr, new BMStringOther().bm2(mainStr.toCharArray(), mainStr.length(), compStr.toCharArray(), compStr.length())));
}
}
