Manacher (tools/manacher.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-20 00:08:16+09:00
• Include: #include "tools/manacher.hpp"

template <typename InputIterator, typename OutputIterator>
void manacher(InputIterator begin, InputIterator end, OutputIterator result);

Given a sequence $(a_0, a_1, \ldots, a_{N - 1})$ from begin and end, it stores the sequence $((l_0, r_0), (l_1, r_1), \ldots, (l_{2N}, r_{2N}))$ to result where the output sequence represents the following facts.

Let $a[l, r)$ denote the continuous subsequence of $a$ created using $a_i$ such that $l \leq i < r$. The longest palindrome centered on $a_i$ is $a[l_{2i + 1}, r_{2i + 1})$. The longest palindrome centered on the $i$-th one of the $N + 1$ boundaries between the elements is $a[l_{2i}, r_{2i})$. (Note that $i$ is $0$-indexed.)

Constraints

• An integer can be read from <InputIterator>.
• A pair of two integers can be written to <OutputIterator>.

Time Complexity

• $O(N)$

License

• CC0

Author

• anqooqie

Depends on

• Minimum excluded value (tools/mex.hpp)

Verified with

• tests/manacher.test.cpp

Code

#ifndef TOOLS_MANACHER_HPP
#define TOOLS_MANACHER_HPP

#include <iterator>
#include <vector>
#include <cstddef>
#include <utility>
#include <algorithm>
#include "tools/mex.hpp"

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void manacher(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> S(begin, end);
    const auto N = S.size();
    {
      ::std::vector<T> new_S(2 * N + 1, ::tools::mex(S.begin(), S.end()));
      for (::std::size_t i = 0; i < N; ++i) {
        new_S[2 * i + 1] = S[i];
      }
      S = ::std::move(new_S);
    }

    ::std::vector<::std::size_t> R(S.size());
    {
      ::std::size_t i = 0;
      ::std::size_t j = 0;
      while (i < S.size()) {
        for (; i >= j && i + j < S.size() && S[i - j] == S[i + j]; ++j);
        R[i] = j;
        ::std::size_t k;
        for (k = 1; i >= k && k + R[i - k] < j; ++k) {
          R[i + k] = R[i - k];
        }
        i += k;
        j -= k;
      }
    }

    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> new_R(S.size());
    for (::std::size_t i = 0; i <= N; ++i) {
      new_R[i * 2] = ::std::make_pair(i - (R[i * 2] - 1) / 2, i + (R[i * 2] - 1) / 2);
    }
    for (::std::size_t i = 0; i < N; ++i) {
      new_R[i * 2 + 1] = ::std::make_pair(i - (R[i * 2 + 1] / 2 - 1), i + R[i * 2 + 1] / 2);
    }
    ::std::move(new_R.begin(), new_R.end(), result);
  }
}

#endif

#line 1 "tools/manacher.hpp"



#include <iterator>
#include <vector>
#include <cstddef>
#include <utility>
#include <algorithm>
#line 1 "tools/mex.hpp"



#include <type_traits>
#line 8 "tools/mex.hpp"
#include <cassert>
#line 10 "tools/mex.hpp"

namespace tools {

  template <typename InputIterator>
  ::std::decay_t<decltype(*::std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end) {
    using T = ::std::decay_t<decltype(*::std::declval<InputIterator>())>;
    const ::std::vector<T> orig(begin, end);
    const ::std::size_t n = orig.size();

    assert(::std::all_of(orig.begin(), orig.end(), [](const auto& o) { return o >= 0; }));

    ::std::vector<bool> exists(n, false);
    for (const ::std::size_t o : orig) {
      if (o < n) {
        exists[o] = true;
      }
    }
    for (::std::size_t i = 0; i < n; ++i) {
      if (!exists[i]) {
        return i;
      }
    }
    return n;
  }
}


#line 10 "tools/manacher.hpp"

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void manacher(const InputIterator begin, const InputIterator end, const OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    ::std::vector<T> S(begin, end);
    const auto N = S.size();
    {
      ::std::vector<T> new_S(2 * N + 1, ::tools::mex(S.begin(), S.end()));
      for (::std::size_t i = 0; i < N; ++i) {
        new_S[2 * i + 1] = S[i];
      }
      S = ::std::move(new_S);
    }

    ::std::vector<::std::size_t> R(S.size());
    {
      ::std::size_t i = 0;
      ::std::size_t j = 0;
      while (i < S.size()) {
        for (; i >= j && i + j < S.size() && S[i - j] == S[i + j]; ++j);
        R[i] = j;
        ::std::size_t k;
        for (k = 1; i >= k && k + R[i - k] < j; ++k) {
          R[i + k] = R[i - k];
        }
        i += k;
        j -= k;
      }
    }

    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> new_R(S.size());
    for (::std::size_t i = 0; i <= N; ++i) {
      new_R[i * 2] = ::std::make_pair(i - (R[i * 2] - 1) / 2, i + (R[i * 2] - 1) / 2);
    }
    for (::std::size_t i = 0; i < N; ++i) {
      new_R[i * 2 + 1] = ::std::make_pair(i - (R[i * 2 + 1] / 2 - 1), i + R[i * 2 + 1] / 2);
    }
    ::std::move(new_R.begin(), new_R.end(), result);
  }
}

Back to top page