場景:字元串比對問題
有一個字元串 a="abcdefg"和另一個字元串b=“bc”,現要判斷a裡面是否包含b,如果存在,傳回第一次出現的位置,如果不存在,傳回-1.
傳統解決方案:暴力比對算法
思路分析:
(1)如果目前字元比對成功,則i++,j++,繼續比對下一個字元
(2)如果比對失敗,使i = i - (j - 1),j = 0,相當于每次比對失敗時,i回溯,j被置0
代碼實作
package com.self.tenAlgorithm;
public class ViolenceMatch {
public static void main(String[] args) {
String a = "abcdefg";
String b = "bc";
int i = violenceMatch(a, b);
System.out.println(i);
}
public static int violenceMatch(String str1,String str2){
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int s1Len = s1.length;
int s2Len = s2.length;
int i = 0;
int j = 0; //索引
while (i < s1Len && j < s2Len){
if(s1[i] == s2[j]){
i++;
j++;
}else{
i = i - (j - 1);
j = 0;
}
}
if(j == s2Len){
return i - j;
}else{
return -1;
}
}
}
暴力比對算法存在問題:會産生大量回溯,每次隻移動一位,若是比對不成功,移動下一位接着判斷,浪費了大量時間.
1.KMP算法
KMP(Knuth-Morris-Pratt),簡稱"KMP算法",是一個解決模式串在文本中是否出現過,如果出現過,最早出現的位置的經典算法,KMP算法就是利用之前判斷過資訊,通過有個next數組,儲存模式串中前後最長公共子序列的長度,每次回溯時,通過next數組找到,前面比對過得位置,省去了大量的計算時間.
KMP算法的應用:
案例:有一個字元串:str1=“BBC ABCDAB ABCDABCDABDE”,子串str2=“ABCDABD”,使用KMP算法判斷子串是否存在,如果存在,傳回第一次出現的位置,如果沒有,傳回-1.
思路分析
(1)用str1的第一個字元和str2的第一個字元去比較,不符合,關鍵詞向後移一位.
(2)重複第一步,還是不符合,向後移
(3)一直重複,知道str1有一個字元與str2的第一個字元符合為止
(4)接着比較字元串和搜尋詞的下一個字元,還是符合
(5)遇到str1有一個字元與str2對應的字元不符合
(6)這時候,可以對str2計算一張"部分比對表",這張表的産生稍後介紹
(7)已知空格與D不比對時,前面六個字元"ABCDAB"是比對的,查表可知,最後一個比對字元B對應的部分比對為2,是以按照下面的公式算出向後移動的位數:
移動位數:已比對的字元數 - 對應的部分比對值
因為6 - 2 = 4,是以将搜尋詞向後移4位
(8)因為空格與C不比對,搜尋詞還要繼續往後移,這時,已比對的字元字元數2(“AB”),對應的部分比對值為0,是以移動數2 - 0 = 2
(9)因為空格與A不比對,繼續後移一位
(10)逐位比較,直到發現C與D不比對,于是,移動位數6 - 2,繼續将搜尋詞向後移動4位
(11)逐位比較,直到搜尋詞的最後一位,發現完全比對,于是搜尋完成,如果還要繼續搜尋(找出全部比對),移動位數7 - 0,再将搜尋詞向後移動7位.
這裡介紹一下比對表是怎麼産生的:
如字元串"bread"
字首:b, br, bre, brea
字尾:read, ead, ad, d
部分比對值就是字首和字尾的最長的共有元素的長度,以"ABCDABD"為例.
"A"的字首和字尾都為空集,共有元素的長度為0
"AB"的字首A,字尾B,共有元素的長度為0
"ABC"的字首為A ,AB,字尾為BC,C,共有元素長度為0
"ABCDA"的字首為A ,AB, ABC, ABCD,字尾為BCDA,CDA,DA,A,共有元素為A,長度為1
"ABCDAB"的字首為ABCDA,ABCD,ABC,AB,A,字尾為:BCDAB,CDAB,DAB,AB,A,共有元素為AB,長度為2
有時候,字元串的頭部和尾部會有重複,比如:“ABCDAB"之中有兩個"AB”,那麼他的部分比對值就是2,搜尋移動的時候,第一個AB向後移動4位,就可以來到第二個AB的位置
KMP步驟:
1)先得到子串的部分比對表
2)使用部分比對表完成KMP比對
代碼實作:
package com.self.tenAlgorithm;
import java.util.Arrays;
public class KMPAlgorithm {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] ints = kmpNext(str2);
System.out.println(Arrays.toString(ints));
int i = kmpSearch(str1, str2, ints);
System.out.println(i);
}
/**
* @param str1 原始字元串
* @param str2 子字元串
* @param next 部分比對表
* @return
*/
public static int kmpSearch(String str1,String str2,int[] next){
for (int i = 0,j = 0; i < str1.length(); i++) {
while (j > 0 && str1.charAt(i) != str2.charAt(j)){
j = next[j - 1];
}
if(str1.charAt(i) == str2.charAt(j)){
j++;
}
if(j == str2.length()){
return i - j + 1;
}
}
return -1;
}
/** 擷取子串的部分比對表
* @param dest
* @return
*/
public static int[] kmpNext(String dest){
int[] next = new int[dest.length()]; //建立一個next數組儲存部分比對值
next[0] = 0;
for (int i = 1 ,j = 0; i < dest.length(); i++) {
while (j > 0 && dest.charAt(i) != dest.charAt(j)){
j = next[j - 1]; //kmp算法的核心點
}
if(dest.charAt(i) == dest.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
}