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