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

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

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

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>
#include <string>
#include "Mylib/String/knuth_morris_pratt.cpp"

namespace hl = haar_lib;

int main() {
  std::string t, p;
  std::cin >> t >> p;

  auto res = hl::knuth_morris_pratt(p).match(t);
  for (auto i : res) std::cout << i << "\n";

  return 0;
}

#line 1 "test/aoj/ALDS1_14_B/main.kmp.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>
#include <string>
#line 3 "Mylib/String/knuth_morris_pratt.cpp"
#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 6 "test/aoj/ALDS1_14_B/main.kmp.test.cpp"

namespace hl = haar_lib;

int main() {
  std::string t, p;
  std::cin >> t >> p;

  auto res = hl::knuth_morris_pratt(p).match(t);
  for (auto i : res) std::cout << i << "\n";

  return 0;
}

Back to top page