主要作用：能夠在線性復(fù)雜度內(nèi)求出一個(gè)串在另一個(gè)串的所有匹配位置。

說(shuō)明：設(shè)模板串是 pattern, 令 next[i] = max{k|[pattern[0..k?1] = pattern[i?k+l..i] 得到。求解next[i]可以使用動(dòng)態(tài)規(guī)劃，即 next[i+1] 可以由next[i]，next[next[i]],…得到。
得到next[i]們數(shù)組之后，設(shè)兩個(gè)指針i和j，分別指向文本串和模式串，成功匹配得向后移動(dòng)j，否則把/移動(dòng)到 next[j]。 當(dāng)j移動(dòng)到模式串末尾時(shí)，就說(shuō)明匹配成功。

首先是next[i]數(shù)組

vector<int> get_next(string ss) { //next[i] ,下標(biāo)為i的 字符前 最長(zhǎng)相等前后綴的長(zhǎng)度int n = ss.size();vector<int>next(n + 1, 0);for (int i = 1; i < n; ++i){int j = i;while (j > 0){// 動(dòng)態(tài)規(guī)劃j = next[j];if (ss[j] == ss[i]){// i+1 是因?yàn)楫?dāng)前的前后綴相等的是其后邊的結(jié)果next[i + 1] = j + 1;break;}}}return next; }

KMP 匹配

vector<int>position;int m = text.size();for (int i = 0, j = 0; i < m; ++i){//cout << "j :" << j << endl;if (j < n && text[i] == pattern[j])++j;else{while (j > 0) //因?yàn)闆](méi)有如果沒(méi)有，next[j] 的值是0{// 回溯到最優(yōu)位置，如果不為0，那么該位置前邊 next[j] -1的元// 素與i位置前邊next[j] -1元素是一樣的j = next[j];if (text[i] == pattern[j])//作用是如果回溯到的地方匹配上了，就從這個(gè)地方開(kāi)始匹配{j++;//因?yàn)檠h(huán)中有 i++break;}}}if (j == n)position.push_back(i - n + 1);}

綜合：

vector<int> find_substring(string pattern, string text) {//next[i] ,下標(biāo)為i的 字符前 最長(zhǎng)相等前后綴的長(zhǎng)度int n = pattern.size();vector<int>next(n + 1, 0);for (int i = 1; i < n; ++i){int j = i;while (j > 0){// 動(dòng)態(tài)規(guī)劃j = next[j];if (pattern[j] == pattern[i]){// i+1 是因?yàn)楫?dāng)前的前后綴相等的是其后邊的結(jié)果next[i + 1] = j + 1; break;}}}vector<int>position;int m = text.size();for (int i = 0, j = 0; i < m; ++i){if (j < n && text[i] == pattern[j])++j;else{while (j > 0){// 回溯到最優(yōu)位置，如果不為0，那么該位置前邊 next[j] -1的元素與i位置前邊next[j] -1元素是一樣的j = next[j];if (text[i] == pattern[j]){j++;break;}}}if (j == n)position.push_back(i - n + 1);}return next; }

詳細(xì)解釋可以看這篇文章：
KMP算法詳解

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的KMP算法之 好理解的模板的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。