运维开发网

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

运维开发网 https://www.qedev.com 2021-08-23 12:53 出处:网络 作者: 冯董事长
目录KMP算法步骤1:先计算子串中的前后缀数组NextC++代码:步骤2:查找子串在母串中出现的位置。总结KMP算法
目录
  • KMP算法
    • 步骤1:先计算子串中的前后缀数组Next
      • C++代码:
    • 步骤2:查找子串在母串中出现的位置。
    • 总结

      KMP算法

      KMP算法作用:字符串匹配

      例如母串S = “aaagoogleaaa”;

      子串T= “google”;

      步骤1:先计算子串中的前后缀数组Next

      KVjHt
      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 (www.cppcns.comi < 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)
          {
        www.cppcns.com      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 = Ne编程客栈xt[j];
              }
          }
          if (j == n)
          {
              return i - j;
          }
          e编程客栈lse
          {
              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;
      }
      

      总结

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

      0

      精彩评论

      暂无评论...
      验证码 换一张
      取 消