字符串匹配算法单模式匹配BM算法

　　一、BM算法
　　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算法比较高效，在实际开发中，特别是一些文本编辑器中，用于实现查找字符串功能。