文字列/Morris–Pratt algorithm（パターンマッチング）
(test/string/morris-pratt.1.test.cpp)

• View this file on GitHub
• Last update: 2023-02-27 16:52:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

• Morris–Pratt algorithm (include/emthrm/string/morris-pratt.hpp)

Code

/*
 * @title 文字列/Morris–Pratt algorithm（パターンマッチング）
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

#include "emthrm/string/morris-pratt.hpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::MorrisPratt(p).match(t)) {
    std::cout << ans << '\n';
  }
  return 0;
}

#line 1 "test/string/morris-pratt.1.test.cpp"
/*
 * @title 文字列/Morris–Pratt algorithm（パターンマッチング）
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
 */

#include <iostream>
#include <string>

#line 1 "include/emthrm/string/morris-pratt.hpp"



#line 5 "include/emthrm/string/morris-pratt.hpp"
#include <vector>

namespace emthrm {

struct MorrisPratt {
  std::string s;
  std::vector<int> border;

  explicit MorrisPratt(const std::string& s) : s(s), border({-1}), j(-1) {
    const int n = s.length();
    for (int i = 0; i < n; ++i) {
      solve(i);
    }
  }

  void add(const char c) {
    s += c;
    solve(s.length() - 1);
  }

  std::vector<int> match(const std::string& t) const {
    const int n = s.length(), m = t.length();
    std::vector<int> res;
    for (int i = 0, k = 0; i < m; ++i) {
      while (k >= 0 && t[i] != s[k]) k = border[k];
      if (++k == n) res.emplace_back(i - n + 1);
    }
    return res;
  }

  int period(const int idx) const { return idx - border[idx]; }

 private:
  int j;

  void solve(const int idx) {
    while (j >= 0 && s[idx] != s[j]) j = border[j];
    border.emplace_back(++j);
  }
};

}  // namespace emthrm


#line 11 "test/string/morris-pratt.1.test.cpp"

int main() {
  std::string t, p;
  std::cin >> t >> p;
  for (const int ans : emthrm::MorrisPratt(p).match(t)) {
    std::cout << ans << '\n';
  }
  return 0;
}

Back to top page