c++ 實(shí)現(xiàn)KMP算法
KMP
KMP算法解決的問(wèn)題
字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中開(kāi)始的位置。
如何做到時(shí)間復(fù)雜度O(N)完成？
思路：
首先判斷兩個(gè)字符串是否為空串，并且str2的長(zhǎng)度是否小于str1的長(zhǎng)度，因?yàn)轭}目要求str1中包含str2。
以上都滿足的情況下，首先定義兩個(gè)變量分別為 x ，y 作為后續(xù)字符串中字符遍歷的下標(biāo)，然后再生成一個(gè)vector容器next，用來(lái)后續(xù)的匹配加速
然后在str2中，做加速操作，也就是 看當(dāng)前 i - 1和之前的所有字符，有沒(méi)有相同的，最大匹配長(zhǎng)度。
從上圖可以看到，下標(biāo)0和1位置的值永遠(yuǎn)都是固定的-1和0,。
x 字符是 i 位置，x 前面的 c 是 i - 1 位置，也就是從下標(biāo)0位置到5位置，找最大的匹配長(zhǎng)度，然后填到 i 的next中。這是循環(huán)中的case1
如果當(dāng)next中的值大于0的時(shí)候，從b開(kāi)始，找到next中的2位置，然后跳轉(zhuǎn)到當(dāng)前位置的next中的坐標(biāo)上，接著進(jìn)行匹配。
最后如果到next為0或者-1的位置上，就標(biāo)記當(dāng)前位置為0，然后到下一個(gè)坐標(biāo)繼續(xù)判斷。
當(dāng) i 遍歷完str2后，循環(huán)結(jié)束，代表next中的值已經(jīng)全部設(shè)置好了。
當(dāng)str1 和 str2 沒(méi)有循環(huán)遍歷到尾部的時(shí)候，只要 str1 中 x 的位置 等于 str2 中 y 的位置 ，x 和 y 就同時(shí)自增。
如果next中的值等于 -1 ，就說(shuō)沒(méi)有匹配成功，x 單獨(dú)自增。讓str1往后挪一位
如果str2中的沒(méi)有匹配成功，就往前找next數(shù)組的值，只要不等于 -1 ，就一直執(zhí)行這個(gè)往前移的過(guò)程。
最后看 y 是否已經(jīng)到了str2的位置，如果到了就說(shuō)明找到了，直接返回 x的位置 減去 y的位置，就是匹配開(kāi)始的位置，否則就是沒(méi)有找到，直接返回 -1
void getNextArray(string str, vector<int>& next)
{
if (str.length() == 1)
{
next.push_back(-1);
}
next.resize(str.length());
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.size())
{
if (str[i - 1] == str[cn])
{
next[i++] = ++cn;
}
else if (cn > 0)
{
cn = next[cn];
}
else {
next[i++] = 0;
}
}
}
int getIndexOf(string s, string m)
{
if (s == "" || m == "" || s.length() < 1 || s.length() < m.length())
{
return -1;
}
int x = 0;
int y = 0;
vector<int> next;
getNextArray(m,next);
while (x < s.length() && y < m.length())
{
if (s[x] == m[y])
{
x++;
y++;
}
else if (next[y] == -1)
{
x++;
}
else {
y = next[y];
}
}
return y == m.length() ? x - y : -1;
}
以上就是c++ 實(shí)現(xiàn)KMP算法的詳細(xì)內(nèi)容，更多關(guān)于c++ KMP算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
全排列算法的非遞歸實(shí)現(xiàn)與遞歸實(shí)現(xiàn)的方法(C++)
本篇文章是對(duì)全排列算法的非遞歸實(shí)現(xiàn)與遞歸實(shí)現(xiàn)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
VC實(shí)現(xiàn)Windows多顯示器編程的方法
這篇文章主要介紹了VC實(shí)現(xiàn)Windows多顯示器編程的方法,涉及VC獲取屏幕分辨率及顯示參數(shù)等技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-10-10
C++實(shí)現(xiàn)團(tuán)購(gòu)訂單管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)團(tuán)購(gòu)訂單管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-12-12
C++11中promise和future機(jī)制是用于并發(fā)編程的一種解決方案，用于在不同線程完成數(shù)據(jù)傳遞（異步操作）。Promise和Future提供了訪問(wèn)異步操作結(jié)果的機(jī)制，可以在線程之間傳遞數(shù)據(jù)和異常消息。本文就來(lái)聊聊二者的使用，希望對(duì)大家有所幫助2022-11-11
線程崩潰不會(huì)導(dǎo)致?JVM?崩潰的原因解析
網(wǎng)上看到一個(gè)很有意思的據(jù)說(shuō)是美團(tuán)的面試題：為什么線程崩潰崩潰不會(huì)導(dǎo)致?JVM?崩潰，這個(gè)問(wèn)題我看了不少回答，但都沒(méi)答到根本原因，所以決定答一答，相信大家看完肯定會(huì)有收獲，本文分以下幾節(jié)來(lái)探討，需要的朋友可以參考下2022-06-06
這篇文章主要介紹了c++類構(gòu)造函數(shù)示例,需要的朋友可以參考下2014-05-05
VS中scanf函數(shù)報(bào)錯(cuò)問(wèn)題的幾種解決方法
本文主要介紹了VS中scanf函數(shù)報(bào)錯(cuò)問(wèn)題的幾種解決方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
算法中排序是十分重要的,而每一個(gè)學(xué)習(xí)計(jì)算機(jī)的都會(huì)在初期的時(shí)候接觸到這種排序,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言冒泡排序與堆排序使用的相關(guān)資料,需要的朋友可以參考下2022-05-05
C語(yǔ)言初識(shí)變量常量字符串轉(zhuǎn)義符及注釋方式簡(jiǎn)介
最強(qiáng)的C語(yǔ)言筆記，此處對(duì)于C語(yǔ)言的基礎(chǔ)部分做一個(gè)簡(jiǎn)要的介紹，作者實(shí)屬初學(xué)，寫博客也是作者學(xué)習(xí)的一個(gè)過(guò)程，若文中內(nèi)容有理解不到位或者有不當(dāng)之處，還請(qǐng)朋友們不吝指正2021-11-11
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無(wú)須手動(dòng)調(diào)用，這篇文章詳細(xì)介紹了構(gòu)造函數(shù)的初始化列表，文章中有詳細(xì)的示例代碼，感興趣的同學(xué)可以參考閱讀2023-04-04