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

• View this file on GitHub
• Last update: 2022-03-23 16:30:51+00:00
• Include: #include "include/string/manachers_algorithm.hpp"

Manacher’s algorithm を用いて、配列中の各位置を中心とする最長の回文である連続部分文字列の長さを求める関数が定義されています。

---

palindrome_length_array(S)

S の各位置を中心とする最長の回文である連続部分文字列の長さを格納した配列 (std::deque<int>) を返します。例えば std::string 型の値 S が "abbba" である場合、それぞれの位置に対して最長の回文の長さは

となるため、返り値は {1 0 1 2 5 2 1 0 1} です。

---

Verified with

• test/string/manachers_algorithm/1.test.cpp

Code

//! @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 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

Back to top page