[数据结构与算法]数据结构与算法-朴素匹配/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) {
              //原理见 DoKMP() 同理，这里是自身的匹配，
              //那自身匹配不是一定可以匹配上？
              //是的，但是我们目的是通过自己匹配求kmp数组。
              //因为i=2，len=0，这样刚好去比较前后缀。
              //abcabg----(text)
              //abcabg----(pattern)
              //失配则 len 借助 kmp[len] 跳到 pattern此时最大前缀的结束位置，省去了无需比较的部分。
              while (len > 0 && pattern[i] != pattern[len + 1]) {
                  len = kmp[len];
              }
              //len+1 表示想要扩展，如果即将扩展的地方字符相等，就可以扩展，长度+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) {
              //失配后，本来嘛，最大长度要直接回到0，
              //聪明的KMP知道这一段完全匹配，虽然失配了
              //但是1-len这段字符串有相同的前后缀，
              //所以跳到0不如跳到最长前缀的结束的那里。
              //比如：
              //abcab|efg----(text)
              //abcab|g----(pattern)  
              //text[i]=e，pattern[len+1]=g时失配
              //一看 kmp[len]等于 2,
              //那么使 len=kmp[len],
              //abcab|efg----(text)
              //ab|cabg----(pattern)  
              //得到 pattern[len]=b，pattern[len+1]=c
              //这样只要比较 text[i]=e和 pattern[len+1]=c
              //不用从头比较了，为什么？
              //因为看此时到 失配之前 的字符串(abcab)最大前后缀
              //text后缀（ab）=pattern后缀(ab)，而pattern后缀(ab)=pattern前缀(ab),
              //所以text后缀（ab）=pattern前缀(ab)，前后缀相等，这一段不需要在比对，所以跳到前缀结束的位置，比较下一位。
              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();
  }