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

目录

  • KMP算法
    • 步骤1:先计算子串中的前后缀数组Next
      • C++代码:
    • 步骤2:查找子串在母串中出现的位置。
    • 总结

      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& 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 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 #include using namespace std; //步骤1:void GetNext(string Tsub, vector& 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 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 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算法】本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注脚本之家的更多内容!

        推荐阅读