欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

一篇文章帶你了解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++中BitBlt的使用方法詳解

    C++中BitBlt的使用方法詳解

    這篇文章主要介紹了C++中BitBlt的使用方法詳解的相關(guān)資料,希望通過本文能幫助到大家,需要的朋友可以參考下
    2017-09-09
  • 淺析C/C++中sort函數(shù)的用法

    淺析C/C++中sort函數(shù)的用法

    做項(xiàng)目的時(shí)候,排序是一種經(jīng)常要用到的操作。如果每次都自己寫個(gè)冒泡之類的O(n^2)排序,不但程序容易超時(shí),而且浪費(fèi)寶貴的時(shí)間,還很有可能寫錯(cuò)。STL里面有個(gè)sort函數(shù),可以直接對(duì)數(shù)組排序,復(fù)雜度為n*log2(n)。
    2014-09-09
  • C語言修煉之路函數(shù)篇真題訓(xùn)練下

    C語言修煉之路函數(shù)篇真題訓(xùn)練下

    函數(shù)是一組一起執(zhí)行一個(gè)任務(wù)的語句。每個(gè) C 程序都至少有一個(gè)函數(shù),即主函數(shù) main() ,所有簡單的程序都可以定義其他額外的函數(shù)
    2022-03-03
  • opencv實(shí)現(xiàn)矩形檢測

    opencv實(shí)現(xiàn)矩形檢測

    這篇文章主要為大家詳細(xì)介紹了opencv實(shí)現(xiàn)矩形檢測,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • C++利用libcurl庫實(shí)現(xiàn)多線程文件下載

    C++利用libcurl庫實(shí)現(xiàn)多線程文件下載

    這篇文章主要為大家詳細(xì)介紹了C++如何利用libcurl庫實(shí)現(xiàn)多線程文件下載,文章的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考下
    2024-01-01
  • C++中std::ios_base::floatfield報(bào)錯(cuò)已解決

    C++中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-09
  • C++內(nèi)存四區(qū)之代碼區(qū)、全局區(qū)、棧區(qū)和堆區(qū)

    C++內(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
  • C語言仿QQ聊天界面抖動(dòng)功能

    C語言仿QQ聊天界面抖動(dòng)功能

    這篇文章主要為大家詳細(xì)介紹了C語言仿QQ聊天界面抖動(dòng)功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-11-11
  • C語言中文件處理全攻略詳解

    C語言中文件處理全攻略詳解

    這篇文章主要為大家詳細(xì)介紹了C語言中文件處理的相關(guān)知識(shí),包括創(chuàng)建、寫入、追加操作解析,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下
    2024-01-01
  • C/C++中文件的隨機(jī)讀寫詳解及其作用介紹

    C/C++中文件的隨機(jī)讀寫詳解及其作用介紹

    這篇文章主要介紹了C/C++中文件的隨機(jī)讀寫詳解及其作用,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09

最新評(píng)論