test/yosupo-judge/zalgorithm/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm
• Link: View error logs on GitHub Actions

Depends on

• join function (Mylib/IO/join.cpp)
• Z-algorithm (Mylib/String/z_algorithm.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>
#include "Mylib/IO/join.cpp"
#include "Mylib/String/z_algorithm.cpp"

namespace hl = haar_lib;

int main() {
  std::string s;
  std::cin >> s;

  auto ans = hl::z_algorithm(s);
  std::cout << hl::join(ans.begin(), ans.end()) << "\n";

  return 0;
}

#line 1 "test/yosupo-judge/zalgorithm/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>
#include <string>
#line 3 "Mylib/IO/join.cpp"
#include <sstream>
#line 5 "Mylib/IO/join.cpp"

namespace haar_lib {
  template <typename Iter>
  std::string join(Iter first, Iter last, std::string delim = " ") {
    std::stringstream s;

    for (auto it = first; it != last; ++it) {
      if (it != first) s << delim;
      s << *it;
    }

    return s.str();
  }
}  // namespace haar_lib
#line 2 "Mylib/String/z_algorithm.cpp"
#include <algorithm>
#include <vector>

namespace haar_lib {
  template <typename Container>
  std::vector<int> z_algorithm(const Container &s) {
    const int n = s.size();
    std::vector<int> ret(n, 0);
    int j = 0;

    for (int i = 1; i < n; ++i) {
      if (i + ret[i - j] < j + ret[j]) {
        ret[i] = ret[i - j];
      } else {
        int k = std::max<int>(0, j + ret[j] - i);
        while (i + k < n and s[k] == s[i + k]) ++k;
        ret[i] = k;
        j      = i;
      }
    }

    ret[0] = n;

    return ret;
  }
}  // namespace haar_lib
#line 7 "test/yosupo-judge/zalgorithm/main.test.cpp"

namespace hl = haar_lib;

int main() {
  std::string s;
  std::cin >> s;

  auto ans = hl::z_algorithm(s);
  std::cout << hl::join(ans.begin(), ans.end()) << "\n";

  return 0;
}

Back to top page