Manacher's Algorithm
(src/string/Manacher.hpp)

• View this file on GitHub
• Last update: 2021-01-15 02:34:06+09:00
• Include: #include "src/string/Manacher.hpp"

Verified with

• test/aizu-online-judge/2934.test.cpp

Code

#pragma once

/**
 * @file Manacher.hpp
 * @brief Manacher's Algorithm
 */

#include <vector>

namespace workspace {

/**
 * @brief Manacher's Algorithm.
 *
 * @param __s String
 * @return Radiuses of the longest palindromic substring with each fixed center.
 */
template <class _Str> std::vector<size_t> Manacher(_Str const &__s) {
  const auto __n = std::size(__s);
  std::vector<size_t> __r(__n);
  for (size_t __i = 0, __c = 0; __i != __n; ++__i)
    if (auto __j = __c * 2 - __i; __j < __n && __c + __r[__c] > __i + __r[__j])
      __r[__i] = __r[__j];
    else {
      __j = __c + __r[__c] - __i;
      while (__i >= __j && __i + __j != __n && __s[__i - __j] == __s[__i + __j])
        ++__j;
      __r[__c = __i] = __j;
    }
  return __r;
}

}  // namespace workspace

#line 2 "src/string/Manacher.hpp"

/**
 * @file Manacher.hpp
 * @brief Manacher's Algorithm
 */

#include <vector>

namespace workspace {

/**
 * @brief Manacher's Algorithm.
 *
 * @param __s String
 * @return Radiuses of the longest palindromic substring with each fixed center.
 */
template <class _Str> std::vector<size_t> Manacher(_Str const &__s) {
  const auto __n = std::size(__s);
  std::vector<size_t> __r(__n);
  for (size_t __i = 0, __c = 0; __i != __n; ++__i)
    if (auto __j = __c * 2 - __i; __j < __n && __c + __r[__c] > __i + __r[__j])
      __r[__i] = __r[__j];
    else {
      __j = __c + __r[__c] - __i;
      while (__i >= __j && __i + __j != __n && __s[__i - __j] == __s[__i + __j])
        ++__j;
      __r[__c = __i] = __j;
    }
  return __r;
}

}  // namespace workspace

Back to top page