|
「一、是什么？」 注意，是KMP算法，不是MMP哈，我沒(méi)有罵人。KMP算法是用來(lái)做字符串匹配的，除了KMP算法，還有暴力匹配算法，也是用來(lái)做字符串匹配的。接下來(lái)先看看暴力匹配算法，你就知道為啥會(huì)出現(xiàn)KMP算法了。注意一點(diǎn)，indexOf方法，其實(shí)是用暴力匹配實(shí)現(xiàn)的，并不是用KMP。 「二、暴力匹配算法：」 「1. 算法思路：」 假如現(xiàn)有兩個(gè)字符串： String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
假設(shè)現(xiàn)在str1匹配到i位置，str2匹配到j(luò)位置，則有： 如果當(dāng)前字符匹配成功，即str1[i] == str2[j]，則i++; j++;，繼續(xù)匹配下一個(gè)字符； 如果匹配不成功，即str1[i] != str2[j]，則令i = i - (j - 1); j = 0;，就是每次匹配失敗，i被回溯，j置為0。
怎么理解這個(gè)過(guò)程呢？ 用i來(lái)遍歷str1，j來(lái)遍歷str2。一開(kāi)始i=0，j=0，所以是不匹配，j就不變，i就一直后移，直到i=4的時(shí)候； 當(dāng)i=4時(shí)，A和A匹配上了，此時(shí)i和j都后移，直到i=10, j=6的時(shí)候，D和空格不匹配； 此時(shí)i=i-j+1=5，j=0，即str2又從第一個(gè)字符A開(kāi)始去跟str1中的第六個(gè)字符B匹配。
通過(guò)上面的描述可以發(fā)現(xiàn)，暴力匹配效率并不高，發(fā)現(xiàn)不匹配之后，回到前面第一次匹配的地方，往后移動(dòng)一位，再開(kāi)始匹配。每次只移動(dòng)一位，會(huì)有大量回溯。 「2. 代碼實(shí)現(xiàn)：」 public class ViolenceMatch {
public static int match(String str1, String str2) {
char[] charArr1 = str1.toCharArray();
char[] charArr2 = str2.toCharArray();
int arr1Len = charArr1.length;
int arr2Len = charArr2.length;
int i = 0; // 遍歷charArr1的索引
int j = 0; // 遍歷charArr2的索引
while(i<arr1Len && j<arr2Len) {
if (charArr1[i] == charArr2[j]) { // 匹配成功
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == arr2Len) {
return i - j;
} else {
return -1;
}
}
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
System.out.println(match(str1, str2));
}
}
「三、KMP算法：」 「1. 介紹：」 KMP算法，是一個(gè)判斷字符串是否在另一個(gè)字符串中出現(xiàn)過(guò)的算法，如果出現(xiàn)過(guò)，返回最早出現(xiàn)的位置。和暴力匹配算法不同的是，KMP算法會(huì)用一個(gè)next數(shù)組來(lái)保存字符串中前后最長(zhǎng)公共子序列的長(zhǎng)度，每次回溯時(shí)，通過(guò)next找到前面匹配過(guò)的位置，這樣就省了大量的時(shí)間。 「2. 案例：」 看了介紹也不知道在說(shuō)什么，直接看案例吧?，F(xiàn)有如下字符串： String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
現(xiàn)在要判斷str1中是否包含str2，如果包含，返回str2在str1中第一次出現(xiàn)的位置，如果沒(méi)有則返回-1。 「思路：」 首先還是用i來(lái)遍歷str1，用j來(lái)遍歷str2； 當(dāng)i=j=0的時(shí)候，i指向的是B，j指向的是A，不匹配； 這個(gè)時(shí)候j不動(dòng)，i后移，指向的是第二個(gè)B，與j所指的A還是不匹配，i繼續(xù)后移； 直到i指向了str1中第一個(gè)空格后面的那個(gè)A，才與j指向的字符匹配了； 到了上一步，A就匹配上了，接著就按同樣的方式去匹配str2中的B、C…… 當(dāng)匹配到str2中的D時(shí)，就發(fā)現(xiàn)匹配不上了，因?yàn)閟tr1中對(duì)應(yīng)的是空格； 到了上面那一步，如果是暴力匹配，那么就會(huì)讓str2中的第一個(gè)字符A與str1中的第二個(gè)字符開(kāi)始進(jìn)行匹配，但是這樣效率低?，F(xiàn)在我們已經(jīng)知道str2中的ABCDAB中str1中是存在的，KMP算法的思想就是利用這個(gè)已知信息，不要把搜索位置移回到前面，因?yàn)榍懊娴目隙ㄊ遣黄ヅ涞?。那么?yīng)該從哪兒開(kāi)始比較呢？ 可以對(duì)str2計(jì)算出一張部分匹配表：
- 已知空格和D不匹配時(shí)，前面六個(gè)字符ABCDAB的匹配的，查表可知，ABCDAB對(duì)應(yīng)的部分匹配值為2，因?yàn)榭梢园凑障旅娴墓接?jì)算出向后移動(dòng)的位數(shù)：
移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
6 - 2 = 4，所以搜索詞向后移動(dòng)四位，即i向后移動(dòng)四位。 - 移動(dòng)四位后，能夠匹配到的是AB，C與str1中的空格還是不匹配，此時(shí)AB對(duì)應(yīng)的部分匹配值是0，所以移動(dòng)位數(shù)為 2 - 0 = 2 位。
…… 「3. 部分匹配表怎么來(lái)的？」 一個(gè)字符串：ABCDAB，它的前綴有A，AB，ABC，ABCD，ABCDA，后綴有B，AB，DAB，CDAB，BCDAB。部分匹配值就是前綴和后綴的最長(zhǎng)的共有元素長(zhǎng)度。這里前綴和后綴共有元素是AB，AB的長(zhǎng)度是2，所以值就是2。上面那張部分匹配表的求值過(guò)程： - A的前綴后綴都是空，共有元素長(zhǎng)度為0；
- AB的前綴是A，后綴是B，共有元素長(zhǎng)度也是0；
- 直到ABCDA，前綴和后綴共有元素長(zhǎng)度是1；
- ABCDAB前綴和后綴共有元素長(zhǎng)度是2；
- ABCDABD前綴和后綴共有元素長(zhǎng)度是0。
「4. KMP算法使用步驟：」 「5. 代碼實(shí)現(xiàn)：」 public class KmpDemo {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
System.out.println(match(str1, str2));
}
/**
* kmp獲取子串在原串中第一次出現(xiàn)的位置
* @param str1 原串
* @param str2 子串
* @return
*/
public static int match(String str1, String str2) {
// 拿到部分匹配值表
int[] table = partMatchTable(str2);
// 遍歷str1
for(int i=0, j=0; i<str1.length(); i++) {
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = table[j-1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
} else {
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
/**
* 獲取str的部分匹配表
* @param str
* @return
*/
private static int[] partMatchTable(String str) {
int[] table = new int[str.length()];
table[0] = 0;
for(int i=1, j=0; i<str.length(); i++) {
while(j > 0 && str.charAt(i) != str.charAt(j)) {
j = table[j-1];
}
if (str.charAt(i) == str.charAt(j)) {
j++;
}
table[i] = j;
}
return table;
}
}
|
