Knuth-Morris-Pratt algorithm
(Mylib/String/knuth_morris_pratt.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

• https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法

Verified with

• test/aoj/ALDS1_14_B/main.kmp.test.cpp

Code

#pragma once
#include <string>
#include <string_view>
#include <vector>

namespace haar_lib {
  class knuth_morris_pratt {
    int M_;
    std::string pattern_;
    std::vector<int> table_;

  public:
    knuth_morris_pratt() {}
    knuth_morris_pratt(std::string p) : M_(p.size()), pattern_(p), table_(M_ + 1) {
      table_[0] = -1;
      table_[1] = 0;

      pattern_.push_back('\0');

      for (int i = 2, j = 0; i <= M_;) {
        if (pattern_[i - 1] == pattern_[j]) {
          table_[i] = j + 1;
          ++i;
          ++j;
        } else if (j > 0) {
          j = table_[j];
        } else {
          table_[i] = 0;
          ++i;
        }
      }
    }

    std::vector<int> match(const std::string_view &s) const {
      std::vector<int> ret;
      const int N = s.size();

      for (int m = 0, i = 0; m + i < N;) {
        if (pattern_[i] == s[m + i]) {
          ++i;
          if (i == M_) {
            ret.push_back(m);
            m += i - table_[i];
            if (i > 0) i = table_[i];
          }
        } else {
          m += i - table_[i];
          if (i > 0) i = table_[i];
        }
      }

      return ret;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/String/knuth_morris_pratt.cpp"
#include <string>
#include <string_view>
#include <vector>

namespace haar_lib {
  class knuth_morris_pratt {
    int M_;
    std::string pattern_;
    std::vector<int> table_;

  public:
    knuth_morris_pratt() {}
    knuth_morris_pratt(std::string p) : M_(p.size()), pattern_(p), table_(M_ + 1) {
      table_[0] = -1;
      table_[1] = 0;

      pattern_.push_back('\0');

      for (int i = 2, j = 0; i <= M_;) {
        if (pattern_[i - 1] == pattern_[j]) {
          table_[i] = j + 1;
          ++i;
          ++j;
        } else if (j > 0) {
          j = table_[j];
        } else {
          table_[i] = 0;
          ++i;
        }
      }
    }

    std::vector<int> match(const std::string_view &s) const {
      std::vector<int> ret;
      const int N = s.size();

      for (int m = 0, i = 0; m + i < N;) {
        if (pattern_[i] == s[m + i]) {
          ++i;
          if (i == M_) {
            ret.push_back(m);
            m += i - table_[i];
            if (i > 0) i = table_[i];
          }
        } else {
          m += i - table_[i];
          if (i > 0) i = table_[i];
        }
      }

      return ret;
    }
  };
}  // namespace haar_lib

Back to top page