一篇文章帶你了解C++的KMP算法
更新時(shí)間:2021年08月15日 14:54:26 作者:馮董事長
這篇文章主要介紹了c++ 實(shí)現(xiàn)KMP算法的示例,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下,希望能給你帶來幫助
KMP算法
KMP算法作用:字符串匹配
例如母串S = “aaagoogleaaa”;
子串T= “google”;
步驟1:先計(jì)算子串中的前后綴數(shù)組Next
g | o | o | g | l | e |
---|---|---|---|---|---|
next[0] | next[1] | next[2] | next[3] | next[4] | next[5] |
-1 | 0 | 0 | 0 | 1 | 0 |
C++代碼:
//步驟1: void GetNext(string Tsub, vector<int>& Next) { int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } } }
步驟2:查找子串在母串中出現(xiàn)的位置。
//步驟2: int KMP(string S, string T, vector<int> Next) { int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; } }
結(jié)合上面兩個(gè)步驟寫出完整代碼:
#include <iostream> #include <vector> using namespace std; //步驟1: void GetNext(string Tsub, vector<int>& Next) { int j = 0, k = -1; Next[0] = k; while (j < Tsub.length() - 1) { if (k == -1 || Tsub[j] == Tsub[k]) { Next[++j] = ++k; } else { k = Next[k]; } } } //步驟2: int KMP(string S, string T, vector<int> Next) { int i = 0, j = 0; int m = S.length(); int n = T.length(); while (i < m && j < n) { if (j == -1 || S[i] == T[j]) { i++; j++; } else { j = Next[j]; } } if (j == n) { return i - j; } else { return -1; } } int main() { string S = "aaagoogleaaa"; string T = "google"; vector<int> Next(T.length()); GetNext(T, Next); int retVal = KMP(S, T, Next); if (retVal == -1) { std::cout << "can't Index" << std::endl; } else { std::cout << "Index :" << retVal << std::endl; } return 0; }
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
C++利用libcurl庫實(shí)現(xiàn)多線程文件下載
這篇文章主要為大家詳細(xì)介紹了C++如何利用libcurl庫實(shí)現(xiàn)多線程文件下載,文章的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考下2024-01-01C++中std::ios_base::floatfield報(bào)錯(cuò)已解決
在C++編程中,設(shè)置浮點(diǎn)數(shù)輸出格式時(shí)可能遇到std::ios_base::floatfield錯(cuò)誤,解決方法包括使用正確的格式化標(biāo)志組合,避免沖突的格式化設(shè)置,以及檢查流狀態(tài)標(biāo)志是否正確,通過這些方法可以有效避免浮點(diǎn)數(shù)格式化錯(cuò)誤,并確保輸出精確2024-09-09C++內(nèi)存四區(qū)之代碼區(qū)、全局區(qū)、棧區(qū)和堆區(qū)
C++編譯器會(huì)把代碼直接分為四個(gè)小區(qū),弄懂這四小區(qū)對(duì)我們理解內(nèi)存有所幫助,所以下面這篇文章主要給大家介紹了關(guān)于C++內(nèi)存四區(qū)之代碼區(qū)、全局區(qū)、棧區(qū)和堆區(qū)的相關(guān)資料,需要的朋友可以參考下2021-07-07