一篇文章帶你了解C++的KMP算法
更新時間：2021年08月15日 14:54:26 作者：馮董事長
這篇文章主要介紹了c++ 實現(xiàn)KMP算法的示例，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下,希望能給你帶來幫助
KMP算法
KMP算法作用：字符串匹配
例如母串S = “aaagoogleaaa”;
子串T= “google”;
步驟1：先計算子串中的前后綴數(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é)合上面兩個步驟寫出完整代碼：
#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++中BitBlt的使用方法詳解的相關(guān)資料,希望通過本文能幫助到大家，需要的朋友可以參考下2017-09-09
做項目的時候，排序是一種經(jīng)常要用到的操作。如果每次都自己寫個冒泡之類的O(n^2)排序，不但程序容易超時，而且浪費寶貴的時間，還很有可能寫錯。STL里面有個sort函數(shù)，可以直接對數(shù)組排序，復雜度為n*log2(n)。2014-09-09
函數(shù)是一組一起執(zhí)行一個任務的語句。每個 C 程序都至少有一個函數(shù)，即主函數(shù) main() ，所有簡單的程序都可以定義其他額外的函數(shù)2022-03-03
這篇文章主要為大家詳細介紹了opencv實現(xiàn)矩形檢測，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要為大家詳細介紹了C++如何利用libcurl庫實現(xiàn)多線程文件下載,文章的示例代碼講解詳細,具有一定的借鑒價值,有需要的小伙伴可以參考下2024-01-01
C++中std::ios_base::floatfield報錯已解決
在C++編程中,設置浮點數(shù)輸出格式時可能遇到std::ios_base::floatfield錯誤,解決方法包括使用正確的格式化標志組合,避免沖突的格式化設置,以及檢查流狀態(tài)標志是否正確,通過這些方法可以有效避免浮點數(shù)格式化錯誤,并確保輸出精確2024-09-09
C++內(nèi)存四區(qū)之代碼區(qū)、全局區(qū)、棧區(qū)和堆區(qū)
C++編譯器會把代碼直接分為四個小區(qū),弄懂這四小區(qū)對我們理解內(nèi)存有所幫助,所以下面這篇文章主要給大家介紹了關(guān)于C++內(nèi)存四區(qū)之代碼區(qū)、全局區(qū)、棧區(qū)和堆區(qū)的相關(guān)資料,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了C語言仿QQ聊天界面抖動功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
這篇文章主要為大家詳細介紹了C語言中文件處理的相關(guān)知識,包括創(chuàng)建、寫入、追加操作解析,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下2024-01-01
這篇文章主要介紹了C/C++中文件的隨機讀寫詳解及其作用，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09