test/string/manachers_algorithm/1.test.cpp

View this file on GitHub
Last update: 2022-03-23 16:30:51+00:00
Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

Manacher's algorithm (include/string/manachers_algorithm.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <iostream>
#include <string>

#include "../../../include/string/manachers_algorithm.hpp"

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

  for (auto&& l : lib::palindrome_length_array(S))
    std::cout << l << ' ';
}

#line 1 "test/string/manachers_algorithm/1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes"
#include <iostream>
#include <string>

#line 1 "include/string/manachers_algorithm.hpp"

//! @file manachers_algorithm.hpp

#ifndef CP_LIBRARY_MANACHERS_ALGORITHM_HPP
#define CP_LIBRARY_MANACHERS_ALGORITHM_HPP

#include <deque>

namespace lib {

//! @brief Compute the longest palindrome lengths centered at each position using Manacher's Algorithm.
//! @tparam Container container type (deduced from parameter)
//! @param src source container (std::string, std::vector, std::deque, ...)
//! @return std::deque<int> containing palindrome lengths ("abbba" -> {1 0 1 2 5 2 1 0 1})
//! @note Time complexity: O(size(src))
template <typename Container>
[[nodiscard]] std::deque<int> palindrome_length_array(const Container& src) {
  const int N = 2 * static_cast<int>(std::size(src)) + 1;
  std::deque<int> res(N);
  int i = 0, j = 0;
  while (i < N) {
    while (i - j >= 0 && i + j < N && ((((i + j) % 2) == 0) || src[(i - j) / 2] == src[(i + j) / 2])) {
      ++j;
    }
    res[i] = j - 1;
    int k  = 1;
    while (i - k >= 0 && k + res[i - k] + 1 < j) {
      res[i + k] = res[i - k];
      ++k;
    }
    i += k;
    j -= k;
  }
  res.pop_front();
  res.pop_back();
  return res;
}

}  // namespace lib

#endif  // CP_LIBRARY_MANACHERS_ALGORITHM_HPP
#line 6 "test/string/manachers_algorithm/1.test.cpp"

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

  for (auto&& l : lib::palindrome_length_array(S))
    std::cout << l << ' ';
}