数据结构与算法-朴素匹配/KMP匹配

本文主要是介绍数据结构与算法-朴素匹配/KMP匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 条件：无

• 题目：无

• 原理：无

• 代码：

  /*
  * Author: Moota
  * Copyright: Moota
  * Description: Written by Moota  
  */
  #include <iostream>  //cin,cout
  #include <iomanip>  //fixed<<setprecision(2)
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <stack>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <cstring>
  #include <cmath> //sqrt,abs
  #include <fstream>  //file
  #include <ctime>
  #include <climits> //数值极限
  //(double)clock() / CLOCKS_PER_SEC <= 1 限制1s跑完程序
  using namespace std;
  
  class Solver {
  public:
      Solver() {
          //取消和c输出输入的同步，加快读取
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout.tie(nullptr);
          //誓死捍卫c++的风格
      }
  
  public:
      void SaveCpp(string name) const {
          fstream input;
          fstream output;
          input.open("moota.cpp", ios::in);
          output.open(name.c_str(), ios::out);
          char c = 'O';
          while (!input.eof()) {
              input.get(c);
              output << c;
          }
          input.close();
          output.close();
      }
  
  protected:
      virtual void BeginPlay() {
      };
  
      virtual void Playing() {
      };
  
      virtual void EndPlay() {
      };
  public:
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  class SpecialSolver : public Solver {
  public:
      typedef long long int lld;
      typedef unsigned long long int ulld;
      static const lld MAX = static_cast<lld>(1e4);
      static const lld INF = static_cast<lld>(1e18);
  private:
      string text, pattern;
      int kmp[MAX];
  private:
      //朴素匹配
      void Normal() {
          const int aSize = text.size() - 1;
          const int bSize = pattern.size() - 1;
          for (int i = 1; i <= aSize; ++i) {
              int k = i;
              for (int j = 1; j <= bSize; ++j) {
                  if (text[k] != pattern[j]) {
                      break;
                  }
                  else {
                      ++k;
                      if (j == bSize) {
                          cout << i << " ";
                      }
                  }
              }
          }
      }
  
      //KMP数组
  
      void GetKMP() {
          kmp[0] = 0;
          //简单的认为一个字符不具有前后缀。
          kmp[1] = 0;
          //len：和自身匹配的字符串的下标。
          //len:也是最长的相同前后缀长度。
          //kmp[len]：到len位置为止（包括len）最大的相同前后缀长度
          int len = 0;
          const int aSize = pattern.size() - 1;
          for (int i = 2; i <= aSize; ++i) {
              //失配后，本来嘛，最大长度要直接回到0，
              //聪明的KMP知道这一段完全匹配，虽然失配了
              //但是1-j这段字符串有相同的前后缀，
              //所以跳到0不如跳到最长前缀的结束的那里。
              //比如：
              //abcabefg
              //abcabg
              //pattern[i]=e，pattern[len+1]=g时失配
              //一看 kmp[len]等于 2,
              //那么回去 pattern[len]=b，pattern[len+1]=c
              //这样只要比较 pattern[i]=e和 pattern[len+1]=c
              //不用从头比较了，为什么？
              //因为此时的最大前后缀
              //text前缀（ab）=pattern后缀(ab)，前后缀相等，无需比较。
              while (len > 0 && pattern[i] != pattern[len + 1]) {
                  len = kmp[len];
              }
              //len+1 表示想要扩展，即将扩展的地方相等，就可以扩展
              if (pattern[i] == pattern[len + 1]) {
                  ++len;
                  kmp[i] = len;
              }
          }
      }
  
      //KMP 匹配
      void DoKMP() {
          int len = 0;
          //此时文本串就不是自身了
          const int aSize = text.size() - 1;
          const int bSize = pattern.size() - 1;
          //现在是匹配文本串，每一位都要匹配，所以从1开始。
          for (int i = 1; i <= aSize; ++i) {
              while (len > 0 && text[i] != pattern[len + 1]) {
                  len = kmp[len];
              }
              if (text[i] == pattern[len + 1]) {
                  ++len;
                  if (len == bSize) {
                      cout << i - bSize + 1 << " ";
                      len = kmp[len];
                  }
              }
          }
      }
  
  protected:
      virtual void BeginPlay() override {
          Solver::BeginPlay();
          //注意修改文件名称
          //SaveCpp("KMP匹配.cpp");
          cin >> text >> pattern;
          text = " " + text;
          pattern = " " + pattern;
      };
  
      virtual void Playing() override {
          Solver::Playing();
          //abcabcabc abc
          cout << "\n朴素匹配：";
          Normal();
          cout << "\nKMP匹配：";
          GetKMP();
          DoKMP();
      };
  
      virtual void EndPlay() override {
          Solver::EndPlay();
      };
  };
  
  SpecialSolver specialSolver;
  
  int main() {
      specialSolver.Play();
  }
  
  

这篇关于数据结构与算法-朴素匹配/KMP匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！