字元串搜尋算法與比對算法的總結

文章目錄

• • BF算法
  • Sunday比對算法
  • KMP算法
  • BM算法

BF算法

暴力破解(就是BF算法),

算法核心思想:首先S[1]和T[1]比較，若相等，則再比較S[2]和T[2]，一直到T[M]為止；若S[1]和T[1]不等，則T向 右移動一個字元的位置，再依次進行比較。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，則比對成功；否則失敗。該算法最壞情況下要進行 M*(N-M+1)次比較，時間複雜度為O(M*N)

比如: String a =“123456789” String b= “23”

其實就是循環 a一個一個字元比對，開始a[0]和b[0]比對，沒有找到，直接不用找b[1]，直接用a[1]和b[0]比對發現已經 找到，然後繼續用

a[2]和b[1]比對發現已經 找到。前且是b字元串末尾。說明已經完全找到。傳回結果

代碼實作:

public class 暴力解法 {
	public static void main(String args[]){  
	      String str1 = "ailkmno";  
	      String str2 = "ilkm";  
	      int n = find(str1,str2);  
	      System.out.println(str2+"在"+str1+"中出現的位置是："+n);  
	        
	  }  
	  public static int find(String str1,String str2){
		  char[] c1=str1.toCharArray();
		  char[] c2=str2.toCharArray();
		  int j=0;
		  int i=0;
		  for(;i<str1.length();){
			  if(j>=str2.length()-1){
				  break;
			  }
			  if(c1[i]==c2[j] ){
				  i=i+1;
				  j=j+1;
			  }else{
				  i=i+1;
			  }
		  }
		  System.out.println(i+"          "+j);
		  return i-str2.length()+1;
	  }
}
           

Sunday比對算法

Sunday算法是Daniel M.Sunday于1990年提出的一種比BM算法搜尋速度更快的算法。

Sunday算法其實思想跟BM算法很相似，隻不過Sunday算法是從前往後比對，在比對失敗時關注的是文本串中參加比對的最末位字元的下一位字元。如果該字元沒有在比對串中出現則直接跳過，即移動步長= 比對串長度+ 1；否則，同BM算法一樣其移動步長=比對串中最右端的該字元到末尾的距離+1。

舉例:

假設我們有如下字元串： 

S = “LESSONS TEARNED IN SOFTWARE TE”;

T = “SOFTWARE”;

(5) k指向的模式串T字元與m指向的主串S字元“E”相等，是以再次移動模式串1位。

代碼實作如下:

import java.util.Arrays;

public class Sunday算法 {

	//建立下一序号表,即記錄字母對應下标
	public static int[] next(char[] T) {
		//初始化序号數組
		int []next=new int[65536];
		//填充壞字元序号
		Arrays.fill(next, -1);
		//填充好字元序号
		for(int j=0;j<T.length;j++) {
			next[T[j]]=j;
		}
		return next;
	}
	

	/**
	 * sunday查找
	 * @param S 正文字元數組
	 * @param T 模式字元數組
	 * @return 比對位置
	 */
	public static int sunday(char[] S,char[] T) {
		//檢查輸入參數有效
		if (S==null||T==null||S.length==0 || T.length==0 ||T.length>S.length){
			return -1;
		}
		
		//擷取下一序号數組
		int next[]=next(T);
		//周遊正文數組
		int delta =S.length-T.length;
		for (int i = 0; i <delta;) {
			//從頭開始比較
			int j=0;
			for (;j<T.length&&i+j<S.length; j++) {
				if (T[j]!=S[i+j]) {
					break;
				}
			}
			//已經完全比對
			if (j==T.length) {
				return i;
			}
			//後移長度不夠
			if (i+T.length>=S.length) {
				return -1;
			}
			//後移偏移距離(根據末位下一字元在模式字元串中的位置判斷偏移距離)
			i+=T.length-next[S[i+T.length]];
		}
		//傳回查找失敗
		return -1;
	}
	public static void main(String[] args) {
		String text="LESSONS TEARNED IN SOFTWARE TE";
		String pattern="SOFTWARE";
		System.out.println("S:\t"+text);
		System.out.println("T:\t"+pattern);
		//測試下一序号數組
		int next[]=next(pattern.toCharArray());
		
		System.out.println("下一序号數組:");
		for(int i=0;i<next.length;i++) {
			if (next[i]!=-1) {
				System.out.println("next['"+(char)i+"']:"+next[i]);
			}
		}
		//測試Sunday查找算法
		System.out.println("Sunday:\t"+sunday(text.toCharArray(),pattern.toCharArray()));
		//Java内置的比對方法,找出第一次比對的index索引
		System.out.println("String:\t"+text.indexOf(pattern));
	}
}
           

KMP算法

KMP是一個解決模式串在文本串是否出現過以及若出現找出最早出現位置的算法.

KMP要做的就是通過一個next數組儲存模式串中前後最長公共子序列的長度以保證每次回溯時通過next數組找到應回溯的位置節省大量無用的回溯比較.

next數組的計算方法:

模式串

ababa

子串

a 字首:無 字尾:無 最長公共子序列長度:0

ab 字首:a 字尾:b 最長公共子序列長度: 0

aba 字首:a ab 字尾:a ba 最長公共子序列長度: 1

abab 字首:a ab aba 字尾:b ab bab 最長公共子序列長度:2

ababa 字首:a ab aba abab 字尾:a ba aba baba 最長公共子序列長度:3

next數組 0 0 1 2 3

KMP算法時間複雜度O(m+n)

算法實作:

public class KMP算法 {

	//求出next數組
	public static int[] kmpnext(String dest) {
		int[] next=new int[dest.length()];
		next[0]=0;
		//i為子序列長度
		for (int i = 1,j=0; i < dest.length(); i++) {
			//循環内的i為字尾下标,j為字首下标,同時j記錄着目前最大公共子序列長度
			while(j>0&&dest.charAt(j)!=dest.charAt(i)) {
				j=next[j-1];
			}
			if (dest.charAt(i)==dest.charAt(j)) {
				j++;
			}
			next[i]=j;
		}
		return next;
	}
	
	//KMP實作
	public static int kmp(String str, String dest,int[] next){//str文本串  dest 模式串
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return 0;
    }
	
	 public static void main(String[] args){
	        String a = "ababa";
	        String b = "ssdfgasdbababa";
	        int[] next = kmpnext(a);
	        int res = kmp(b, a,next);
	        System.out.println(res);
	        for(int i = 0; i < next.length; i++){
	            System.out.println(next[i]);            
	        }
	        System.out.println(next.length);
	    }

}
           

BM算法

Boyer-Moore算法，簡稱BM算法。該算法從模式串的尾部開始比對，且擁有在最壞情況下O(N)的時間複雜度。在實踐中，比KMP算法的實際效能高。

例如,給定文本串"HERE IS A SIMPLE EXAMPLE"和模式串"EXAMPLE",現要查找模式串是否在文本串中,如果存在,傳回模式串在文本串中的位置.

1. 首先，"文本串"與"模式串"頭部對齊，從尾部開始比較。"S"與"E"不比對。這時，“S"就被稱為"壞字元”（bad character），即不比對的字元，它對應着模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中（相當于最右出現位置是-1），這意味着可以把模式串後移6-(-1)=7位，進而直接移到"S"的後一位。 

   

2. 依然從尾部開始比較，發現"P"與"E"不比對，是以"P"是"壞字元"。但是，"P"包含在模式串"EXAMPLE"之中。因為“P”這個“壞字元”對應着模式串的第6位（從0開始編号），且在模式串中的最右出現位置為4，是以，将模式串後移6-4=2位，兩個"P"對齊。

   

3. 依次比較，得到 “MPLE”比對，稱為"好字尾"（good suffix），即所有尾部比對的字元串。注意，“MPLE”、“PLE”、“LE”、"E"都是好字尾。

   

4. 發現“I”與“A”不比對：“I”是壞字元。如果是根據壞字元規則，此時模式串應該後移2-(-1)=3位。

   

5. 繼續從尾部開始比較，“X”與“E”不比對，是以“X”是“好字元”，根據“好字元規則”，後移 6 - 1 = 5位。這是，“X”與“X”對齊。

   

6. 依次從尾部開始比較,所有字元都能比對,查找成功.

   

   壞字元算法:

   

   壞字元算法實作:

/**
 * 壞字元忽略映射
 * @param T 模式字元數組
 * @return 壞字元忽略映射
 */
	public static int[] bmBc(char[] T) {
		//初始忽略數組
		/*
		 * 為了友善起見,就直接把UTF8編碼用65536個字元全表示了,
		 *  這樣就不會漏掉哪個字元了
		 */
		int []bmBc = new int[65536];
		//填充壞字元序号
		Arrays.fill(bmBc, -1);
		//填充好字元序号(以最後位置為準)
		int m=T.length;
		/*
		 * for循環bmBc[x[i]]中x[i]表示模式串中的第i個字元
		 * 為什麼循環中,i從小到大的順序計算呢?技巧就在這兒了
		 * 在同一個字元多次出現的時候以最靠右的那個字元到尾部的距離為最終距離.
		 * 當然,如果是沒在模式串中出現的字元,距離就是m
		 */
		for(int i=0;i<m;i++) {
			bmBc[T[i]]=m-1-i;
		}
		//傳回忽略數組
		return bmBc;
	}
           

好字尾算法:

(2) 模式串中沒有子串比對上字尾,此時需要尋找模式串的一個最長字首,并讓該字首等于 好字尾 的字尾 ,尋找到該字首後,讓該字首和好字尾對齊即可.

為了實作 好字尾 規則,需要定義一個數組suffix[],其中suffix[i]=s表示 以i為邊界,與模式串字尾比對的最大長度,如下圖所示,用公式表述:滿足P[i-s,m]的最大長度.

計算字尾長度數組代碼:

/**
	 * 計算字尾長度數組
	 * @param P 模式字元數組
	 * @return  字尾長度數組
	 */
	public static int[] suffix(char[] P) {
		//初始化字尾數組
		int m=P.length;
		int []suffix=new int[m];
		//計算字尾數組
		suffix[m-1]=m;
		for(int i=m-2;i>=0;--i) {
			int q=i;
			while(q>=0&&P[q]==P[m-1-i+q]) {
				q--;
			}
			suffix[i]=i-q;
		}
		return suffix;
	}
           

/**
	 * 好字尾忽略映射
	 * @param P 模式字元映射
	 * @return 字尾數組(字元對應模式字元數組中的最後位置)
	 */
	public static int[] bmgs(char[] P) {
		//初始化忽略數組
		int m=P.length;
		int[] bmgs=new int[m];
		//擷取字尾數組
		int[] suffix=suffix(P);
		//指派預設取值
		Arrays.fill(bmgs, m);
		//模式串中沒有子串比對上好字尾,但找到一個最大字首
		for (int i = m-1,j=0; i >=0; --i) {
			if (suffix[i]==i+1) {
				for (; j < m-1-i; ++j) {
					if (bmgs[j]==m) {
						bmgs[j]=m-1-i;
					}
				}
			}
		}
		//模式串中有子串比對上好字尾
		for (int i = 0; i < m-2; ++i) {
			bmgs[m-1-suffix[i]]=m-1-i;
		}
		return bmgs;
	}
           

/**
	 * BM算法比對
	 * @param T 正文字元數組
	 * @param P 模式字元數組
	 * @return 比對位置
	 */
	public static int BM(char[] T,char[] P) {
		//擷取忽略映射
		int []bmBc=bmBc(P);
		int []bmGs=bmgs(P);
		//比對字元串
		int j=0;
		int n=T.length;
		int m=P.length;
		while(j<=n-m) {
			int i=m-1;
			while(i>=0&&P[i]==T[i+j]) {
				i--;
			}
			//成功比對字元
			if (i<0) {
				return j;
			}
			//往後移動位置
			j+=Math.max(bmGs[i], bmBc[T[i+j]]-m+1+i);
			
		}
		return -1;
	}
           

測試代碼:

public static void main(String[] args) {
		String text="HERE IS A SIMPLE EXAMPLE";
		String pattern="EXAMPLE";
		System.out.println(BM(text.toCharArray(),pattern.toCharArray()));
	}