一篇文章帶你了解C++的KMP算法
更新時間：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é)合上面兩個步驟寫出完整代碼：
#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)文章
pybind11: C++ 工程提供 Python 接口的實(shí)例代碼
這篇文章主要介紹了pybind11: C++ 工程如何提供 Python 接口,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-09-09
C++稀疏矩陣的各種基本運(yùn)算并實(shí)現(xiàn)加法乘法
今天小編就為大家分享一篇關(guān)于C++稀疏矩陣的各種基本運(yùn)算并實(shí)現(xiàn)加法乘法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-02-02
c++中#include <>與#include""的區(qū)別詳細(xì)解析
<>先去系統(tǒng)目錄中找頭文件，如果沒有在到當(dāng)前目錄下找。所以像標(biāo)準(zhǔn)的頭文件 stdio.h、stdlib.h等用這個方法2013-10-10
本文給大家講解的是在從C語言過渡到C++中的引用的區(qū)別及簡單示例，有需要的小伙伴可以參考下2017-07-07
這篇文章主要為大家詳細(xì)介紹了C語言中動態(tài)內(nèi)存管理的相關(guān)知識，以及常見的動態(tài)內(nèi)存的錯誤，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-07-07
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)循環(huán)雙鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
C語言中const,volatile,restrict的用法總結(jié)
以下是對C語言中const,volatile,restrict的用法進(jìn)行了詳細(xì)的總結(jié)介紹，需要的朋友可以過來參考下2013-10-10
map是STL的一個關(guān)聯(lián)容器，它以<key,value>一對一的形式存儲，且map的內(nèi)部自建一個紅黑樹，使得其可以自動排序，本文就介紹一下C++ map的簡單使用，感興趣的可以了解一下2021-05-05
如何使用C語言實(shí)現(xiàn)細(xì)菌的繁殖與擴(kuò)散
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)細(xì)菌的繁殖與擴(kuò)散，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(76.最小窗口子串),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07