字符串匹配--BM算法

谁借莪１个温暖的怀抱￠ 2022-01-14 01:41 223阅读 0赞

最近在准备面试，看到有关字符串匹配的问题，才知道BM算法(只怪平时在规则中没有深入研究一些算法)！！！

那好！就介绍一下什么是BM算法吧，来看下百度百科里面的解释吧：

在[计算机科学][Link 1]里，**Boyer-Moore字符串搜索算法**是一种非常高效的[字符串搜索算法][Link 2]。它由Bob Boyer和J Strother Moore设计于1977年。此[算法][Link 3]仅对搜索目标[字符串][Link 4]（关键字）进行[预处理][Link 5]，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

那就下面详细介绍一下BM算法吧，当然篇博客也会借助一些其他文章做一个汇总，也是笔者在理解BM算法的笔记，希望对读者有所帮助，话不多说，直接进入正题啦！

了解一个算法首先需要知道该算法的原理和思想，这个至关重要，那就先对BM算法的原理切入做个切入点：

BM算法基于**后缀比较**（从右向左比较 的方法），而BM算法实际是包含了**两个并行算法**：**坏字符规则** 和**好后缀规则。**

**（推荐大家看一篇关于BM算法的思想博客：[字符串匹配BM算法学习][BM]）**

**首先需要明确两个算法规则：**

**1、坏字符规则：**

后移位数 = 坏字符的位置 - 模式串中的坏字符上一次出现位置

如果"坏字符"不包含在模式串之中，则上一次出现位置为 -1。以下面这两个字符串为例

![20190616090721776.png][]

因为"G"与"H"不匹配，所以"G"被称为"坏字符"，它出现在模式串（模式串就是FGH）的第2位（从0开始编号），在模式串中的上一次出现位置为1，所以后移 2 - 1 = 1位

![2019061609094183.png][]

** 2、好后缀规则 **

后移位数 = 好后缀的位置 - 模式串中的上一次出现位置

举例来说，如果模式串"ABCDEFABCD"的后一个"AB"是"好后缀"。那么它的位置是6（从0开始计算，取最后的"B"的值），在模式串中的上一次出现位置是1（第一个"B"的位置），所以后移 6 - 1 = 5位，前一个"AB"移到后一个"AB"的位置。

再举一个例子，如果模式串"ABCDEFGH"的"EF"是好后缀，则"EF"的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 - (-1) = 6位，即整个字符串移到"F"的后一位。

这个规则有三个注意点：

1.  "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
2.  如果"好后缀"在模式串中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
3.  如果"好后缀"有多个，这时应该选择最长的那个"好后缀"且它的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位，其他好后缀上一次出现的位置都不在头部

**现在有这样一个需求：我想知道一个字符串在另外一个字符串中是否出现，比如**

String originText = "ABCDEFGHHH"
    String moduleText = "FGGH";

判断moduleText 在originText 中是否出现，如果出现则返回出现的位置的索引，如果没有出现则返回-1。（当然，在这里我暂且摒弃字符串对象API的场景，仅仅从算法入手！！！）。同时也要说明一个问题：moduleText作为匹配的字符串，也叫作模式串（也叫作搜索词），originText作为被查找的字符串，也称作主串。

1. 首先，主串与模式串头部对齐，从尾部开始比较。这个思想的效率很高，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前10个字符（整体上）肯定不是要找的结果。我们看到，"C"与"H"不匹配。这时，"C"就被称为"坏字符"（bad character），这时用坏字符规则得到的是3，用好后缀规则得到的是-1，选择大的作为后移位数，这里选择3

![20190616092128908.png][]

2、依然从尾部开始比较，发现"F"与"H"不匹配，所以"F"是"坏字符"。

![20190616092410952.png][]

一次类比，最终得到

![20190616094300670.png][]

实现代码如下

package www.supermaster.cn.text;
    
    /**
     * 坏字符规则: 后移位数 = 坏字符的位置 - 模式串中的坏字符上一次出现位置
     * 
     * 好后缀规则:后移位数 = 好后缀的位置 - 模式串中的上一次出现位置
     * 
     */
    public class BMTest
    {
    
    	public static void main(String[] args)
    	{
    		// 主串
    		String originText = "ABCDEFGHHFGHH";
    		// 模式串
    		String moduleText = "FGH";
    		// 坏字符规则表
    		//	        int[] badCharacterArray = badCharacter(originString,moduleString);
    
    		System.out.println("主串：" + originText);
    		System.out.println("模式串：" + moduleText);
    
    		int index = bmMatch(originText, moduleText);
    		System.out.println("匹配的下标：" + index);
    	}
    
    	/**
    	 * @Description:[BM匹配字符串]
    	 * @Method: bmMatch
    	 * @param originText
    	 *            主串
    	 * @param moduleText
    	 *            模式串
    	 * @return 若匹配成功，返回下标，否则返回-1
    	 */
    	public static int bmMatch(String originText, String moduleText)
    	{
    		// 主串
    		if (originText == null || originText.length() <= 0)
    		{
    			return -1;
    		}
    		// 模式串
    		if (moduleText == null || moduleText.length() <= 0)
    		{
    			return -1;
    		}
    
    		//如果模式串的长度大于主串的长度，那么一定不匹配
    		if (moduleText.length() > originText.length())
    		{
    			return -1;
    		}
    
    		int moduleSuffix = moduleText.length() - 1;// 模式串最大长度值
    		int moduleIndex = moduleSuffix; // 初始化模式串起始Index
    		int originIndex = moduleSuffix; // 初始化主串初始化Index
    		//
    		for (int index = originIndex; originIndex < originText.length() && moduleIndex >= 0;)
    		{
    			char och = originText.charAt(originIndex); // 主串某个位置的Char
    			char mch = moduleText.charAt(moduleIndex); // 模式串某个位置的Char
    			//
    			if (och == mch)
    			{
    				originIndex--;
    				moduleIndex--;
    			}
    			else
    			{
    				// 坏字符规则
    				int badMove = badCharacterRule(moduleText, och, moduleIndex);
    				// 好字符规则
    				int goodMove = goodCharacterRule(moduleText, moduleIndex);
    
    				// 主串位置不动，模式串向右移动
    				originIndex = index + Math.max(badMove, goodMove);
    				moduleIndex = moduleSuffix;
    				// index就是中间变量
    				index = originIndex;
    			}
    		}
    
    		if (moduleIndex < 0)
    		{
    			// 多减了一次
    			return originIndex + 1;
    		}
    
    		return -1;
    	}
    
    	/**
    	 * @Description:[利用好后缀规则计算移动位数]
    	 * @Method: goodCharacterRule
    	 * @param moduleText
    	 * @param charSuffix
    	 * @return
    	 */
    	private static int goodCharacterRule(String moduleText, int charSuffix)
    	{
    		int result = -1;
    		// 模式串长度
    		int moduleMax = moduleText.length();
    
    		// 好字符数
    		int charSize = moduleMax - 1 - charSuffix;
    
    		for (; charSize > 0; charSize--)
    		{
    			String startText = moduleText.substring(0, charSize);
    			String endText = moduleText.substring(moduleMax - charSize, moduleMax);
    			if (startText.equals(endText))
    			{
    				result = moduleMax - charSize;
    			}
    		}
    
    		return result;
    	}
    
    	/**
    	 * @Description:[利用坏字符规则计算移动位数]
    	 * @Method: badCharacterRule
    	 * @param moduleText
    	 * @param badChar
    	 * @param charSuffix
    	 * @return
    	 */
    	private static int badCharacterRule(String moduleText, char badChar, int charSuffix)
    	{
    		return charSuffix - moduleText.lastIndexOf(badChar, charSuffix);
    	}
    
    }

这篇文章主要是针对面试情况，代码才是主要展示显示，后续会继续完善！读者有好的提议请留言，促使我们共同进步！！

持续完善中..............

\----------------------------------------------------------------------------------------  
作者：编码世界  
来源：CSDN  
原文：[https://blog.csdn.net/dgxin\_605/article/details/92360040][https_blog.csdn.net_dgxin_605_article_details_92360040]  
版权声明：本文为博主原创文章，转载请附上博文链接！

[Link 1]: https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/9132
[Link 2]: https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/6287150
[Link 3]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
[Link 4]: https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6%E4%B8%B2/1017763
[Link 5]: https://baike.baidu.com/item/%E9%A2%84%E5%A4%84%E7%90%86/7833652
[BM]: https://blog.csdn.net/qq_28453017/article/details/81813892
[20190616090721776.png]: /images/20220113/35767989d87b45c2a1fd1bf7571e1ab4.png
[2019061609094183.png]: /images/20220113/e009498492554fcd80dda1bfe633d1a6.png
[20190616092128908.png]: /images/20220113/31974a2ff22d4f84ae76839c33489977.png
[20190616092410952.png]: /images/20220113/49f92a91fbc24261826bf9cd7af72d06.png
[20190616094300670.png]: /images/20220113/b51d8d74c3044e2b9b87096ae9e56f21.png
[https_blog.csdn.net_dgxin_605_article_details_92360040]: https://blog.csdn.net/dgxin_605/article/details/92360040