C++的KMP算法是怎么用的

這篇文章主要講解了“C++的KMP算法是怎么用的”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++的KMP算法是怎么用的”吧！

目錄

• KMP算法

• 步驟1：先計算子串中的前后綴數組Next

• C++代碼：

• 步驟2：查找子串在母串中出現的位置。

• 總結

KMP算法

KMP算法作用：字符串匹配

例如母串S = “aaagoogleaaa”;

子串T= “google”;

步驟1：先計算子串中的前后綴數組Next

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：查找子串在母串中出現的位置。

//步驟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;
    }
}

結合上面兩個步驟寫出完整代碼：

#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;
}

感謝各位的閱讀，以上就是“C++的KMP算法是怎么用的”的內容了，經過本文的學習后，相信大家對C++的KMP算法是怎么用的這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！