Java-BM字符串匹配算法丶Java教程网

关注
Java-BM字符串匹配算法丶Java教程网www.shan-machinery.com

BM 匹配算法遵循一个条件、两个规则:

一、条件:

模式串与主串匹配是从字符串的尾部开始,即从后向前

二、规则:

1. 坏字符规则:模式串与主串依次匹配的过程中,若主串中出现未匹配的字符,则这个字符称为坏字符,这个字符在模式串匹配的位置记作 Si;坏字符在模式串中的下标记作 Xi,若不存在,则为 -1;x = Si - Xi 的差就是模式串要滑动的距离,单纯靠坏字符规则是不行的,因为 x 在有些情况下会是负数

2. 好后缀规则:模式串与主串匹配中会出现匹配上的子串,这个子串就被称为好后缀。好后缀在模式串中的前部分也是存在的,则模式串的滑动距离为 模式串的长度减去好后缀在模式串中出现的起始位置,若好后缀在模式串中是不存在的,那么再看好后缀是否存在子串是否为模式串的前缀子串,若是,则模式串滑动的距离为模式串的长度减去前缀子串的长度

三、取坏字符和好后缀的最大值作为模式串滑动的距离

代码如下:

/** * BM 匹配算法: * 坏字符规则: 坏字符在模式串中出现的下标 Si,坏字符在模式串中存在的下标 Xi,模式串滑动的距离 x = Si - Xi * 好后缀规则: 好后缀在模式串中存在时的偏移距离 suffix; 好后缀最长的,能跟模式串前缀子串匹配时的偏移距离 prefix */public class BmMatch { // 坏字符:利用哈希表模式串中各字符在模式串中的位置private static int SIZE = 256;public static void generateBC(char[] b, int m, int[] bc){for(int i = 0; i < SIZE; i++){bc[i] = -1;}for(int i = 0; i < m; i++){int ascii = b[i];bc[ascii] = i;}}// 好后缀:求解 suffix 和 prefixpublic static 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++){int j = i;int k = 0;while(j >= 0 && b[i] == b[m - 1 - k]){j--;k++;suffix[k] = j + 1;}if(j == -1) prefix[k] = true;}}// 返回好后缀的滑动距离public static 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 https://www.shan-machinery.com