关键词查找【Boyer-Moore 算法】

1、【Boyer-Moore 算法】

【算法】哪种算法有分数复杂度？- BoyerMoore字符串匹配_哔哩哔哩_bilibili

BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征，加快了搜索的步骤。
BM算法实际上包含两个并行的算法（也就是两个启发策略）：坏字符算法（bad-character shift）和好后缀算法（good-suffix shift）。这两种算法的目的就是让模式串每次向右移动尽可能大的距离（即上面的BM( )尽可能大）。

一般情况下，比KMP算法快3-5倍

package com.vedeng;public class BoyerMoore {private static final int NO_OF_CHARS = 256;// 预处理坏字符规则private static void badCharHeuristic(char[] str, int size, int[] badChar) {for (int i = 0; i < NO_OF_CHARS; i++) {badChar[i] = -1;}for (int i = 0; i < size; i++) {badChar[(int) str[i]] = i;}}// Boyer-Moore算法实现public static void search(char[] txt, char[] pat) {int m = pat.length;int n = txt.length;int[] badChar = new int[NO_OF_CHARS];// 预处理坏字符规则badCharHeuristic(pat, m, badChar);int s = 0; // s是shift的缩写，表示模式串相对于文本串的偏移while (s <= (n - m)) {int j = m - 1;// 从右向左匹配while (j >= 0 && pat[j] == txt[s + j]) {j--;}// 如果匹配成功，打印匹配的位置if (j < 0) {System.out.println("Patterns occur at shift = " + s);// 根据好后缀规则计算下一个可能的偏移s += (s + m < n) ? m - badChar[txt[s + m]] : 1;} else {// 根据坏字符规则计算下一个可能的偏移s += Math.max(1, j - badChar[txt[s + j]]);}}}public static void main(String[] args) {char[] txt = "ABAAABCD".toCharArray();char[] pat = "ABC".toCharArray();search(txt, pat);}
}