問題描述
指定文本串：aabaabaaf和模式串：aabaaf
使用KMP算法判斷模式串是否在文本串中出現(xiàn)過阅茶？
假定模式串的長度小于文本串
思路解析
BF算法的問題是：模式串已經(jīng)匹配到最后一位了發(fā)現(xiàn)不一樣矾柜，需要將文本串和模式串的指針都往后退跺讯，導(dǎo)致有很多的重復(fù)匹配，效率很低。
KMP算法的思路是间聊，在發(fā)現(xiàn)某個(gè)字符不匹配的時(shí)候族购，充分利用前面已經(jīng)匹配過的結(jié)果壳贪，不要把“搜索指針”回退到已經(jīng)比較過的位置，而是把模式串往后移動(dòng)到合適的位置繼續(xù)比較寝杖。KMP算法只需要對(duì)文本串搜索一次违施，時(shí)間復(fù)雜度是O(n)。
檢索過程圖解
如上圖所示瑟幕，在遇到不匹配的時(shí)候醉拓，依靠“部分匹配表”可知伟姐，最后一個(gè)匹配字符a對(duì)應(yīng)的部分匹配值是2，可以根據(jù)下面的公式計(jì)算出模式串的移動(dòng)位數(shù)亿卤。
移動(dòng)位數(shù) = 已經(jīng)匹配的字符串長度 - 對(duì)應(yīng)的部分匹配值
aabaa是已經(jīng)匹配的字符串愤兵，長度是5；aabaa對(duì)應(yīng)的部分匹配值是2排吴，因此將模式串往右移動(dòng)3位秆乳，就可以繼續(xù)匹配了，KMP就是通過這個(gè)“部分匹配表”避免了搜索指針的回退钻哩。
部分匹配表
要理解部分匹配表屹堰，需要了解兩個(gè)概念：前綴子串、后綴子串
- 前綴子串：包含首字母街氢，不包含尾字母的所有子串
- 后綴子串：包含尾字母扯键，不包含首字母的所有子串
例如：單詞"bread"
- 前綴子串："b","br","bre","brea"
- 后綴子串："d","ad","ead","read"
部分匹配表中的數(shù)值含義是：當(dāng)前這個(gè)字符前面的字符串中，相等的前綴子串和后綴子串的最大的長度珊肃。計(jì)算下aabaa的部分匹配表：
- a：前綴子串集合和后綴子串集合都是空集荣刑，相等的前后綴子串的最大長度是0
- aa：前綴子串集合是[a]，后綴子串集合是[a]伦乔，相等的前后綴子串的最大長度是1
- aab：前綴子串集合是[a,aa]厉亏，后綴子串集合是[b,ab]，相等的前后綴子串的最大長度是0
- aaba烈和，前綴子串集合是[a,aa,aab]爱只，后綴子串集合是[a,ba,aba]，相等的前后綴子串的最大長度是1
- aabaa招刹，前綴子串集合是[a,aa,aab,aaba]恬试，后綴子串集合是[a,aa,baa,abaa]，相等的前后綴子串的最大長度是2
- aabaaf疯暑，前綴子串集合是[a,aa,aab,aaba,aabaa]忘渔，后綴子串集合是[f,af,aaf,baaf,abaaf]，相等的前后綴子串的最大長度是0
“部分匹配表”的實(shí)質(zhì)是缰儿，模式字符串中有時(shí)會(huì)有重復(fù)的子串畦粮，例如：aabaa的左右兩邊都有aa，那么該字符串的部分匹配值就是2乖阵，那么在發(fā)現(xiàn)aabaaf中的f不匹配的時(shí)候宣赔，只需要將aabaaf這個(gè)模式串往右移動(dòng)3個(gè)位置，就可以讓第一個(gè)aa來到第二個(gè)aa的位置瞪浸。
代碼實(shí)現(xiàn)
package org.javaadu.string;
import java.util.List;
public class StringSearchDemo {
public static void main(String[] args) {
String text = "aabaabaaf";
String pattern = "aabaaf";
boolean kmpRes = kmpSearch(text, pattern);
System.out.println("kmpRes:" + kmpRes);
}
/**
* 利用KMP算法求解pattern是否在text中出現(xiàn)過
*
* @param text 文本串
* @param pattern 模式串
* @return pattern在text中出現(xiàn)儒将，則返回true，否則返回false
*/
public static boolean kmpSearch(String text, String pattern) {
//部分匹配數(shù)組对蒲，就是很多算法實(shí)現(xiàn)中的next數(shù)組
int[] partMatchTable = buildPartMatchTable(pattern);
//text中的指針
int i = 0;
//pattern中的指針
int j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
//字符匹配钩蚊，則兩個(gè)指針同時(shí)后移
i++;
j++;
} else if (j > 0) {
//字符失配贡翘，則利用next數(shù)組，異動(dòng)j指針砰逻，避免i指針回退
j = partMatchTable[j - 1];
} else {
//pattern中的第一個(gè)字符就失配了
i++;
}
if (j == pattern.length()) {
//搜索成功
return true;
}
}
return false;
}
private static int[] buildPartMatchTable(String pattern) {
//初始化
int[] partMatchTable = new int[pattern.length()];
int prefixLen = 0;
next[0] = 0;
int i = 1;
while (i < pattern.length()) {
//pattern[prefixLen]鸣驱，表示目前最長相等子串的最后一位
//pattern[i]，表示目前正在處理的子串的最后一位的字符
if (pattern.charAt(prefixLen) == pattern.charAt(i)) {
//如果它倆相等蝠咆，說明找到了更長的相等子串
prefixLen++;
partMatchTable[i] = prefixLen;
i++;//處理下一個(gè)i的字符
} else {
//如果不相等踊东，則需要嘗試下更短1位的子串是否滿足要求，因此這里要把再次循環(huán)嘗試下：僅僅改變prefixLen的值刚操，不改變i的值
prefixLen = next[prefixLen - 1];
if (prefixLen == 0) {
//如果實(shí)在沒有合適的闸翅，則說明當(dāng)前正在處理的子串的最長相等前后綴的長度是0
partMatchTable[i] = 0;
i++;//處理下一個(gè)i的字符
}
}
}
return partMatchTable;
}
}
參考資料
- https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
- https://www.bilibili.com/video/BV1AY4y157yL/?vd_source=a7cf54b1d9550c0b692539a82b982181
- https://www.bilibili.com/video/BV1PD4y1o7nd/?spm_id_from=333.337.search-card.all.click&vd_source=33b7a49ff9ee993637d7533b74ed12a5
