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

• View this file on GitHub
• Last update: 2021-01-15 02:49:56+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2934

Depends on

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

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2934"

#include <iostream>

#include "src/string/Manacher.hpp"

int main() {
  using namespace workspace;
  size_t n;
  std::string s;
  std::cin >> n >> s;
  auto r = Manacher(s);
  for (size_t k = 2; k <= n; ++k) {
    bool fail = false;
    for (size_t i = k - 1; i < n; i += k - 1)
      if (r[i] < std::min(k, n - i)) fail = true;
    if (!fail) {
      std::cout << k << "\n";
      return 0;
    }
  }
}

#line 1 "test/aizu-online-judge/2934.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2934"

#include <iostream>

#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
#line 6 "test/aizu-online-judge/2934.test.cpp"

int main() {
  using namespace workspace;
  size_t n;
  std::string s;
  std::cin >> n >> s;
  auto r = Manacher(s);
  for (size_t k = 2; k <= n; ++k) {
    bool fail = false;
    for (size_t i = k - 1; i < n; i += k - 1)
      if (r[i] < std::min(k, n - i)) fail = true;
    if (!fail) {
      std::cout << k << "\n";
      return 0;
    }
  }
}

Back to top page