字元串比對算法

比對原理：

字元串A ：a b c d e f h

字元串B ： c d e f

通過觀察可知，字元串B是字元串A的子串，且B在A中第一次出現的位置是2，是以直接傳回2，若無法比對到子串則傳回-1，一般我們統一将這裡的A稱為主串，B稱為模式串。

方法一：BF算法（Brute Force 暴力算法）

暴力比對法，即從主串的首位開始，把主串和模式串的字元進行逐個比較，若第一位就不同，則将模式串進行後移一位，再次重新開始比較；若第一位相同，則進行主串與模式串的第二位，第三位的依次比較。

1. 假設主串的長度是m，模式串的長度是n，BF算法的最壞時間複雜度為O(mn)；
2. 該種方法實作簡單，但是執行效率很低；

方法二：RK算法（Rabin-Karp 哈希比對算法）

哈希比對法，即将原先主串和模式串的字元比較轉換成對應哈希值比較，這樣的要容易得多。具體的哈希轉換方法有很多，例如，按位相加法、轉換成26進制法。由于主串通常要長于模式串，把整個主串轉化成hashcode是沒有意義的，隻有比較主串當中和模式串等長的子串才有意義，當哈希值相等時，再模仿BF算法，進行兩個字元串的逐項比較。

hashcode = hash（string）

1. 哈希法可以通過優化字元串累加方法，即新子串的hash值都用上一次子串進行簡單的增量來計算；
2. 通使用優化方法，最終RK算法的時間複雜度可以優化為O(n);
3. 與BF算法相比，免去了很多無謂的字元比較，時間複雜度上有很大提高；
4. RK算法的缺點在于哈希沖突，每一次哈希沖突時都要進行子串和模式串的逐個比較，如果沖突過多，RK算法就會退化成BF算法。

RK算法代碼如下

.

public static int rabinKarp (String str, String pattern){   
	//主串長度   
	int m = str.length();   
	//模式串的長度   
	int n = pattern.length();   
	//計算模式串的hash值 
	int patternCode = hash(pattern);  
	//計算主串當中第一個和模式串等長的子串hash值  
	int strCode = hash(str.substring(0,n));

	//用模式串的hash值和主串的局部hash值比較。
	//如果比對，則進行精确比較；如果不比對，計算主串中相鄰子串的hash值。   
	for (int i = 0; i<m-n+1; i++){
	        if(strCode == patternCode && compareString(i, str, pattern)){           
				return i;     
				}
			//如果不是最後一輪，更新主串從i到i+n的hash值
	        if(i<m-n){
	            strCode = nextHash(str, strCode, i, n);
	        
				}
	    }
	return -1;}

private static int hash(String str){    
	int hashcode = 0;    
	//這裡采用最簡單的hashcode計算方式：    
	//把a當做1，把b當中2，把c當中3.....然後按位相加    
	for (int i = 0; i < str.length(); i++) {        
		hashcode += str.charAt(i)-'a';    
		}    
	return hashcode;
}

private static int nextHash(String str, int hash, int index, int n){    
	hash -= str.charAt(index)-'a';    
	hash += str.charAt(index+n)-'a';    
	return hash;
}

private static boolean compareString(int i, String str, String pattern) {
   String strSub = str.substring(i, i+pattern.length());    
   return strSub.equals(pattern);
}

public static void main(String[] args) {    
	String str = "aacdesadsdfer";    
	String pattern = "adsd";    
	System.out.println("第一次出現的位置:" + rabinKarp(str, pattern));
           

方法三：BM算法（壞字元和好字尾算法）

壞字元規則

即是指模式串和子串當中不比對的字元，當模式串和主串的第一個等長子串比較時，從右側開始确定壞字元（檢測順序相反，是從字元串最右側向最左側檢測），如果壞字元在模式串中不存在，則直接把模式串挪到主串壞字元的下一位。

1. 壞字元的位置越靠右，下一輪模式串的挪動跨度就可能越長，節省的比較次數也就越多；

//在模式串中，查找index下标之前的字元是否和壞字元比對
private static int findCharacter(String pattern, char badCharacter, int index) {    
	for(int i= index-1; i>=0; i--){        
		if(pattern.charAt(i) == badCharacter){            
			return i;        
			}    
		}  
		//模式串不存在該字元，傳回-1    
	return -1;
	}

public static int boyerMoore(String str, String pattern) {    
	int strLength = str.length();    
	int patternLength = pattern.length();    
	//模式串的起始位置    
	int start = 0;    
	while (start <= strLength - patternLength) {        
		int i;        
		//從後向前，逐個字元比較        
		for (i = patternLength - 1; i >= 0; i--) {            
			if (str.charAt(start+i) != pattern.charAt(i))
			   //發現壞字元，跳出比較，i記錄了壞字元的位置                
				break;        
				}        
			if (i < 0) {
			    //比對成功，傳回第一次比對的下标位置            
			    return start;        
			    }        
		//尋找壞字元在模式串中的對應        
		int charIndex = findCharacter(pattern, str.charAt(start+i), i);        
		//計算壞字元産生的位移        
		int bcOffset = charIndex>=0 ? i-charIndex : i+1;        
		start += bcOffset;    
		}    
		return -1;
}

public static void main(String[] args) {    
	String str = "GTTATAGCTGGTAGCGGCGAA";    
	String pattern = "GTAGCGGCG";    
	int index = boyerMoore(str, pattern);    
	System.out.println("首次出現位置：" + index);
}
           

好字尾規則

好字尾就是指模式串和子串當中相比對的字尾。即當子串和模式串不比對時，但模式串和子串存在好字尾，且在模式串中可以找到與好字尾相同的片段，這樣就可以直接移動模式串中的相同片段與模式串的好字尾對齊，進而實作快速位移；但是當不存在這樣的相同片段時，切記不可一次性把模式串移動到好字尾的後面，要判斷模式串的字首是否與好字尾的字尾相比對，以免移動過多而錯過。

何時采用壞字元或者好字尾規則，并沒有直接結論，需要分别計算下一輪模式串移動的長度并進行比較，可以使模式串移動更多的規則，就是更好的方法。

方法四：KMP算法（最長可比對前字尾子串算法）

即在已比對的字首當中尋找到最長可比對字尾子串和最長可比對字首子串，在下一輪直接把兩者對齊，進而實作模式串的快速移動。而提前将這個字首（next數組）找出來則是KMP算法的重點。

詳細算法原理講解建議參看視訊：【天勤公開課】KMP算法易懂版

這裡直接附上代碼：

// KMP算法主體邏輯。str是主串，pattern是模式串
public static int kmp(String str, String pattern) {
//預處理，生成next數組
int[] next = getNexts(pattern);
int j = 0;
//主循環，周遊主串字元
for (int i = 0; i < str.length(); i++) {
while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
//遇到壞字元時，查詢next數組并改變模式串的起點
            j = next[j];
}
if (str.charAt(i) == pattern.charAt(j)) {
            j++;
}
if (j == pattern.length()) {
//比對成功，傳回下标
return i - pattern.length() + 1;
}
}
return -1;
}


// 生成Next數組
private static int[] getNexts(String pattern) {
int[] next = new int[pattern.length()];
int j = 0;
for (int i=2; i<pattern.length(); i++) {
while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
//從next[i+1]的求解回溯到 next[j]
            j = next[j];
}
if (pattern.charAt(j) == pattern.charAt(i-1)) {
            j++;
}
next[i] = j;
}
return next;
}

public static void main(String[] args) {
String str = "ATGTGAGCTGGTGTGTGCFAA";
String pattern = "GTGTGCF";
int index = kmp(str, pattern);
System.out.println("首次出現位置：" + index);
}