test/yosupo-judge/enumerate_palindromes/main.manacher.test.cpp

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

Depends on

• join function (Mylib/IO/join.cpp)
• Manacher algorithm (Mylib/String/manacher.cpp)

Code

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

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

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string S;
  std::cin >> S;

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

  return 0;
}

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

#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/manacher.cpp"
#include <optional>
#include <vector>

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

    for (int cur = 0; cur < n; ++cur) {
      int left = center - (cur - center);

      if (left >= 0 and cur + ret[left] < center + ret[center]) {
        ret[cur] = ret[left];
      } else {
        int len = center + ret[center] - cur;
        while (cur - len >= 0 and cur + len < n and s[cur - len] == s[cur + len]) ++len;
        ret[cur] = len;
        center   = cur;
      }
    }

    return ret;
  }

  template <typename Container>
  std::vector<int> manacher_all(const Container &s) {
    using T     = typename Container::value_type;
    const int N = s.size();
    std::vector<int> ret(2 * N - 1);

    {
      auto res = manacher(s);
      for (int i = 0; i < N; ++i) {
        ret[i * 2] = res[i] * 2 - 1;
      }
    }

    {
      std::vector<std::optional<T>> T;
      for (int i = 0; i < N; ++i) {
        if (i) T.push_back(std::nullopt);
        T.push_back(s[i]);
      }

      auto res = manacher(T);
      for (int i = 0; i < N - 1; ++i) {
        ret[i * 2 + 1] = (res[i * 2 + 1] / 2) * 2;
      }
    }

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

namespace hl = haar_lib;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  std::string S;
  std::cin >> S;

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

  return 0;
}

Back to top page