一篇文章带你了解C++的KMP算法

• kmp算法
• 步骤1：先计算子串中的前后缀数组next

kmp算法

kmp算法作用：字符串匹配

例如母串s = “aaagoogleaaa”;

子串t= “google”;

步骤1：先计算子串中的前后缀数组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：查找子串在母串中出现的位置。

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

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！