Test/String/ZAlgorithm.test.cpp

• View this file on GitHub
• Last update: 2024-12-27 17:07:26+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B

Depends on

• Library/String/ZAlgorithm.hpp

Code

#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B"

#include "./../../Library/String/ZAlgorithm.hpp"


#include <iostream>


using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
  Preprocessing() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
  };
} _Preprocessing;

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

  std::string s = t + "$" + p;
  auto za = mtd::ZAlgorithm(s);

  int tsz = t.size();
  int ssz = s.size();
  auto ans = za.find(tsz, ssz - 1, tsz);

  for (const auto& it : ans) { cout << it - tsz - 1 << endl; }
}

#line 1 "Test/String/ZAlgorithm.test.cpp"
#define PROBLEM \
  "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/14/ALDS1_14_B"

#line 2 "Library/String/ZAlgorithm.hpp"

#include <deque>

#include <iostream>

#include <string>

#include <vector>


namespace mtd {
  /**
   * Z algorithmによりZ Arrayを構築する
   * O(N)
   * S[0..]とS[i..]の共通接頭辞数
   * ex) aaabaaaab -> [9, 2, 1, 0, 3, 4, 2, 1, 0]
   */
  class ZAlgorithm {
    const std::vector<int> m_zArray;

    static auto constrcutZArray(const std::string& str) {
      auto sz = static_cast<int>(str.size());
      auto zArray = std::vector<int>(sz);
      zArray[0] = sz;

      int i = 1, j = 0;
      while (i < sz) {
        while (i + j < sz && str[j] == str[i + j]) ++j;
        zArray[i] = j;
        if (j == 0) {
          ++i;
          continue;
        }
        int k = 1;
        while (i + k < sz && k + zArray[k] < j) {
          zArray[i + k] = zArray[k];
          ++k;
        }
        i += k;
        j -= k;
      }
      return zArray;
    }

  public:
    ZAlgorithm(const std::string& str) : m_zArray(constrcutZArray(str)) {}

    /* i∈[l,r]でz[i]=sizeとなるindexを返す */
    auto find(int l, int r, int size) const {
      std::deque<int> dq;
      for (int i = l; i <= r; ++i)
        if (m_zArray[i] == size) { dq.emplace_back(i); }
      return dq;
    }

    /* output for debug */
    void debugOutput() const {
      std::cerr << "-- z array --" << std::endl;
      for (const auto& x : m_zArray) { std::cerr << x << " "; }
      std::cerr << std::endl;
    }

    auto get() const { return m_zArray; }
  };
}  // namespace mtd

#line 5 "Test/String/ZAlgorithm.test.cpp"

#line 7 "Test/String/ZAlgorithm.test.cpp"

using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
  Preprocessing() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
  };
} _Preprocessing;

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

  std::string s = t + "$" + p;
  auto za = mtd::ZAlgorithm(s);

  int tsz = t.size();
  int ssz = s.size();
  auto ans = za.find(tsz, ssz - 1, tsz);

  for (const auto& it : ans) { cout << it - tsz - 1 << endl; }
}

Back to top page