程序员必知算法----BM字符串查找算法

灰太狼 2022-01-11 00:45 249阅读 0赞

BM字符串查找算法，由Boyer,Moore提出，因而得名。

该算法和KMP算法思想一样，都是需要先进行预处理，然后在每次进行匹配失败时，根据预处理的结果，快速找到下一次继续匹配的位置。

与KMP不同的是，BM算法在每次匹配时都从后往前开始匹配，这样可以确保在模式字符串的后面字符出现匹配失败时能够快速的进行下面的匹配。如果我们从前往后进行匹配检查，那么当出现前面字符匹配正确，而在最后一个字符出现匹配错误时，白白的浪费了前面的匹配检查的时间。

也许你会说，从后面往前进行匹配检查也会出现同样的问题，我承认，的确存在这样的问题，而且这也是最坏的情况，对于下面实现的算法，该问题的时间复杂度会是O(M\*N），但是完整实现的BM算法能够保证在最坏的情况下提供线性级别的运行时间。

我们在匹配检测前，需要预先准备一个数组right\[\]，该数组记录着模式字符串中各个字符在模式字符串中最后出现的位置，即最靠右边的位置。通过这个数组，在每次匹配检测失败后，能够快速的找到下一轮进行匹配检测的新位置。

在字符串的查找过程中，我们使用索引i在目标字符串中从前往后移动，使用索引j在模式字符串中从后往前移动，j的取值范围为\[M-1,0\]。

在每一轮从后往前进行匹配的过程中，如果匹配成功，那么就继续往前进行匹配检测；如果匹配失败，那么要根据不同情况，适当的调整下一轮匹配的位置。具体匹配失败可分为两下两种情况：

（1）造成匹配失败的字符没有出现在模式字符串中，此时需要将模式字符串向右移动（实际编程实现中，是通过将i增加j+1来实现的），如果移动少于这个偏移量，那么都会使得模式字符串中有字符和目标字符串中该匹配失败的字符对齐，从而再次匹配失败。

（2）造成匹配失败的字符出现在模式字符串中，此时需要根据预处理的right\[\]数组来确定需要移动的偏移量，使用right数组可以使得目标字符串中的该字符与模式字符串中的最右边相同字符对齐（这里需要注意的是，此时有可能会出现模式字符串左移的情况，这时，为了保证匹配的过程是一值往后移动的，需要至少使得i增加1,）。

算法实现如下所示：

package com.algorithm.stringsearch;
    
    import java.util.Arrays;
    
    //字符串查找算法，Boyer-Moore算法
    public class BoyerMoore {
    	private String pat;
    	private int[] right;
    	
    	public BoyerMoore(String pat){
    		this.pat=pat;
    		int R=256;
    		right=new int[R];
    		Arrays.fill(right, -1);
    		int patLen=pat.length();
    		for(int i=0;i<patLen;i++){
    			right[pat.charAt(i)]=i;
    		}
    	}
    	
    	public int search(String str){
    		int i,j,N=str.length(),M=pat.length();
    		int skip;
    		for(i=0;i<=N-M;i+=skip){
    			skip=0;
    			for(j=M-1;j>=0;j--){
    				if(str.charAt(i+j)!=pat.charAt(j)){
    					skip=j-right[str.charAt(i+j)];
    					if(skip<1){//保证模式字符串时不断向后移动的
    						skip=1;
    					}
    					break;
    				}
    			}
    			if(skip==0) return i;
    		}
    		return N;
    	}
    	
    	public static void main(String[] args){
    		String t1="bcbaabacaababacaa";
    		String t2="ababac";
    		BoyerMoore bm=new BoyerMoore(t2);
    		System.out.println(bm.search(t1));
    	}
    }

假设目标字符串的长度为N，模式字符串的长度为M，分析一下这个算法的时间复杂度，在最坏的情况下，时间复杂度为O(M\*N)，但是在一般情况下，该算法的时间复杂度为O(N/M)。

需要说明的是，完整的Boyer-Moore算法通过复杂的预处理，可以保证最坏情况下的时间复杂度也为线性级别的。