轉(zhuǎn)載請(qǐng)注明出處: KMP算法及優(yōu)化
今天看到同學(xué)在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)書上的KMP算法遣疯，忽然發(fā)覺自己又把KMP算法忘掉了，以前就已經(jīng)忘過(guò)一次，看樣子還是沒(méi)有真正的掌握它，這回學(xué)聰明點(diǎn)柑晒，再次搞明白后記錄下來(lái)。
一般字符串匹配過(guò)程
KMP算法是字符串匹配算法的一種改進(jìn)版眷射，一般的字符串匹配算法是：從主串(目標(biāo)字符串)和模式串(待匹配字符串)的第一個(gè)字符開始比較匙赞，如果相等則繼續(xù)匹配下一個(gè)字符， 如果不相等則從主串的下一個(gè)字符開始匹配妖碉，直到模式串被匹配完涌庭，則匹配成功，或主串被匹配完且模式串未匹配完欧宜，則匹配失敗坐榆。匹配過(guò)程入下圖：
這種實(shí)現(xiàn)方式是最簡(jiǎn)單的， 但也是低效的冗茸，因?yàn)榈谌纹ヅ浣Y(jié)束后的第四次和第五次是沒(méi)有必要的席镀。
分析
第三次匹配在j = 0(a)和i = 2(a)處開始羹铅，在j = 4(c)和i = 6(b)處失敗，這意味著模式串和主串中：j = 0(a)和i = 2(a)愉昆、j = 1(b)和i = 3(b)、j = 2(c)和i = 4(c)麻蹋、j = 3(a)和i = 5(a)這四個(gè)字符相互匹配跛溉。
分析模式串的前3個(gè)字符：模式串的第一個(gè)字符j = 0是a，j = 1(b)扮授、j = 2(c)這兩個(gè)字符和j = 0(a)不同芳室，因此以這兩個(gè)字符開頭的匹配必定失敗，在第三次匹配中刹勃，主串中i = 3(b)堪侯、i = 4(c)和模式串j = 1(b)、j = 2(c)相互匹配荔仁，因此匹配失敗后伍宦，可以直接跳過(guò)主串中i = 3(b)、i = 4(c)這兩個(gè)字符的匹配乏梁。
繼續(xù)分析模式串的j = 3(a)和j = 4(c)這兩個(gè)字符次洼，如果模式串匹配到j = 4(c)這個(gè)字符才失敗的話，因?yàn)?code>j = 4(c)的前一個(gè)字符j = 3(a)和第一個(gè)字符j = 0(a)是相同的遇骑，結(jié)合上一個(gè)分析得知：
1)：下一次匹配中主串已經(jīng)跳過(guò)了和
j = 3(a)前兩個(gè)相互匹配的字符i = 3(b)卖毁、i = 4(c)，將從i = 5(a)開始匹配落萎。
2)：j = 3(a)和i = 5(a)相互匹配亥啦。
因此下一次匹配認(rèn)為j = 3(a)和i = 5(a)已經(jīng)匹配過(guò)了，匹配從j = 4(b)和i = 6(b)開始练链，這樣的話也跳過(guò)了j = 3(a)這個(gè)字符的匹配翔脱。
同理可得第二次匹配也是沒(méi)必要的。
KMP算法
KMP算法匹配過(guò)程
利用KMP算法匹配的過(guò)程如下圖：
KMP算法的改進(jìn)之處在于：能夠知道在匹配失敗后兑宇，有多少字符是不需要進(jìn)行匹配可以直接跳過(guò)的碍侦，匹配失敗后，下一次匹配從什么地方開始能夠有效的減少不必要的匹配過(guò)程隶糕。
next[n]求解方法
由上面的分析可以發(fā)現(xiàn)瓷产，KMP算法的核心在于對(duì)模式串本身的分析，其分析結(jié)果能提供在j = n位置匹配失敗時(shí)枚驻，從j = 0到j = n - 1這個(gè)子串中前綴和后綴的最長(zhǎng)公共匹配的字符數(shù)濒旦，這樣說(shuō)可能比較難以理解，看下圖：
在得到子串前綴和后綴的最長(zhǎng)公共匹配字符數(shù)l后再登，以后在i = x,j = n處匹配失敗時(shí)尔邓，可以直接從i = x,j = l處繼續(xù)匹配(證明過(guò)程參考:嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》4.3章)晾剖，這樣問(wèn)題就很明顯了，我們要求出n和l對(duì)應(yīng)的值梯嗽，其中n是模式串字符數(shù)組的下標(biāo)齿尽，l的有序集合通常稱之為next數(shù)組，前面兩個(gè)模式串的next數(shù)組和下標(biāo)n的對(duì)應(yīng)如下：
模式串2完整匹配過(guò)程
有了這個(gè)next數(shù)組灯节，那么在匹配的過(guò)程中我們就能在j = n處匹配失敗后循头，根據(jù)next[n]的值進(jìn)行偏移，其中next[0]固定為-1炎疆，代表在當(dāng)前i這個(gè)位置整個(gè)模式串和主串都無(wú)法匹配成功卡骂，要從下一個(gè)位置i = i + 1及j = 0處開始匹配，模式串2的匹配過(guò)程如下：
現(xiàn)在知道了next數(shù)組的作用形入，也知道在有next數(shù)組時(shí)的匹配過(guò)程全跨，那么剩下的問(wèn)題就是如何通過(guò)代碼求出next數(shù)組及匹配過(guò)程了。
求
next數(shù)組的過(guò)程可以認(rèn)為是將模式串拆分成n個(gè)子串亿遂，分別對(duì)每個(gè)子串求前綴和后綴的最長(zhǎng)公共匹配字符數(shù)l浓若，這一點(diǎn)可以通過(guò)上圖(最長(zhǎng)公共匹配字符數(shù))看出來(lái)(沒(méi)有畫出l=0時(shí)的圖解)看出來(lái)。
代碼實(shí)現(xiàn)
求next數(shù)組的代碼如下：
void get_next(string pattern, int next[]) {
int i = 0; // i用來(lái)記錄當(dāng)前計(jì)算的next數(shù)組元素的下標(biāo)崩掘， 同時(shí)也作為模式串本身被匹配到的位置的下標(biāo)
int j = 0; // j == -1 代表從在i的位置模式串無(wú)法匹配成功七嫌，從下一個(gè)位置開始匹配
next[0] = -1; // next[0]固定為-1
int p_len = pattern.length();
while (++i < p_len) {
if (pattern[i] == pattern[j]) {
// j是用來(lái)記錄當(dāng)前模式串匹配到的位置的下標(biāo)， 這就意味著當(dāng)j = l時(shí)苞慢，
// 則在pattern[j]這個(gè)字符前面已經(jīng)有l(wèi) - 1個(gè)成功匹配,
// 即子串前綴和后綴的最長(zhǎng)公共匹配字符數(shù)有l(wèi) - 1個(gè)诵原。
next[i] = j++;
} else {
next[i] = j;
j = 0;
if (pattern[i] == pattern[j]) {
j++;
}
}
}
}
根據(jù)next數(shù)組求模式串在主串中的位置代碼如下：
int search(string source, string pattern, int next[]) {
int i = 0;
int j = 0;
int p_len = pattern.length();
int s_len = source.length();
while (j < p_len && i < s_len) {
if (j == -1 || source[i] == pattern[j]) {
i++;
j++;
}
else {
j = next[j];
}
}
if (j < pattern.length())
return -1;
else
return i - pattern.length();
}
測(cè)試代碼如下：
int main() {
string source = "ABCDABCEAAAABASABCDABCADABCDABCEAABCDABCEAAABASABCDABCAABLAKABCDABABCDABCEAAADSFDABCADABCDABCEAAABCDABCEAAABASABCDABCADABCDABCEAAABLAKABLAKK";
// string pattern = "abcaaabcab";
string pattern = "ABCDABCEAAABASABCDABCADABCDABCEAAABLAK";
int next[pattern.length()] = { NULL };
get_next(pattern, next);
cout << "next數(shù)組: \t";
for (int i = 0; i < pattern.length(); i++)
cout << next[i] << " ";
cout << endl;
int pos = search(source, pattern, next);
if (-1 != pos) {
cout << "匹配成功，模式串在主串中首次出現(xiàn)的位置是: 第" << pos + 1 << "位";
getchar();
return 0;
} else {
cout << "匹配失敗";
}
getchar();
return 0;
}
執(zhí)行結(jié)果：
next數(shù)組: -1 0 0 0 0 1 2 3 0 1 1 1 2 1 0 1 2 3 4 5 6 7 1 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1
匹配成功挽放，模式串在主串中首次出現(xiàn)的位置是: 第97位
KMP算法優(yōu)化
再回過(guò)頭去看模式串2的next數(shù)組的圖：
如果模式串和主串的匹配在j = 6(b)處失敗的話绍赛，根據(jù)j = next[6] = 1得知下一次匹配從j = 1處開始，j = 1處的字符和j = 6處的字符同為c辑畦，因此這次匹配必定會(huì)失敗吗蚌。
同樣的，模式串和主串的匹配在j = 7(c)處或在j = 9(b)處失敗的話纯出，根據(jù)next數(shù)組偏移后下一次匹配也必定會(huì)失敗蚯妇。
考慮如果模式串是: aaaac，根據(jù)一般的KMP算法求出的next數(shù)組及匹配過(guò)程如下：
顯而易見暂筝，在第二次匹配失敗后箩言，第三、四焕襟、五次匹配都是沒(méi)有意義的陨收，j = next[3]、j = next[2]鸵赖、j = next[1]务漩、j = next[0]這四處的字符都是a拄衰，在j = 3(a)處匹配失敗時(shí)，根據(jù)模式串本身就應(yīng)該可以得出結(jié)論：可以跳過(guò)j = 2(a)饵骨、j = 1(a)翘悉、j = 0(a)的匹配，直接從i = i + 1 居触、j = 0處開始匹配镐确，所以優(yōu)化過(guò)后的next數(shù)組應(yīng)該是：
代碼實(shí)現(xiàn)
優(yōu)化后的求next數(shù)組的代碼如下：
void get_next(string pattern, int next[]) {
int i = 0; // i用來(lái)記錄當(dāng)前計(jì)算的next數(shù)組元素的下標(biāo)， 同時(shí)也作為模式串本身被匹配到的位置的下標(biāo)
int j = 0; // j == -1 代表從在i的位置模式串無(wú)法匹配成功饼煞，從下一個(gè)位置開始匹配
next[0] = -1; // next[0]固定為-1
int p_len = pattern.length();
while (++i < p_len) {
if (pattern[i] == pattern[j]) {
// j是用來(lái)記錄當(dāng)前模式串匹配到的位置的下標(biāo)， 這就意味著當(dāng)j = l時(shí)诗越，
// 則在pattern[j]這個(gè)字符前面已經(jīng)有l(wèi) - 1個(gè)成功匹配,
// 即子串前綴和后綴的最長(zhǎng)公共匹配字符數(shù)有l(wèi) - 1個(gè)砖瞧。
next[i] = j++;
// 當(dāng)根據(jù)next[i]偏移后的字符與偏移前的字符向同時(shí)
// 那么這次的偏移是沒(méi)有意義的，因?yàn)槠ヅ浔囟〞?huì)失敗
// 所以可以一直往前偏移嚷狞，直到
// 1): 偏移前的字符和偏移后的字符不相同块促。
// 2): next[i] == -1
while (next[i] != -1 && pattern[i] == pattern[next[i]]) {
next[i] = next[next[i]];
}
} else {
next[i] = j;
j = 0;
if (pattern[i] == pattern[j]) {
j++;
}
}
}
}
結(jié)尾
希望本文能對(duì)你有幫助， 如果有什么問(wèn)題床未， 歡迎探討竭翠。
參考文獻(xiàn)
嚴(yán)蔚敏的《數(shù)據(jù)結(jié)構(gòu)》4.3章
kmp算法--百度百科
