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算法是怎么用的这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！