文字列/Manacher
(test/string/manacher.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_palindromes

Depends on

• Manacher (include/emthrm/string/manacher.hpp)

Code

/*
 * @title 文字列/Manacher
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_palindromes
 */

#include <iostream>
#include <string>

#include "emthrm/string/manacher.hpp"

int main() {
  std::string s;
  std::cin >> s;
  const int n = s.length();
  emthrm::Manacher manacher(s);
  for (int i = 0; i < n; ++i) {
    std::cout << (manacher.odd(i) - 1) * 2 + 1;
    if (i + 1 == n) [[unlikely]] {
      std::cout << '\n';
    } else {
      std::cout << ' ' << manacher.even(i) * 2 << ' ';
    }
  }
  return 0;
}

#line 1 "test/string/manacher.test.cpp"
/*
 * @title 文字列/Manacher
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_palindromes
 */

#include <iostream>
#include <string>

#line 1 "include/emthrm/string/manacher.hpp"



#include <vector>

namespace emthrm {

struct Manacher {
  template <typename T>
  explicit Manacher(const T& s) {
    T str;
    int n = s.size();
    str.reserve(n * 2 + 1);
    for (int i = 0; i < n; ++i) {
      str.push_back(s[i]);
      str.push_back('$');
    }
    str.pop_back();
    n = str.size();
    radius.resize(n);
    for (int i = 0, j = 1; i < n;) {
      while (i - j >= 0 && i + j < n && str[i - j] == str[i + j]) ++j;
      radius[i] = j;
      int k = 1;
      for (; i - k >= 0 && i + k < n && k + radius[i - k] < j; ++k) {
        radius[i + k] = radius[i - k];
      }
      i += k;
      j -= k;
    }
  }

  int odd(const int idx) const { return (radius[idx * 2] + 1) / 2; }

  int even(const int idx) const { return radius[idx * 2 + 1] / 2; }

  bool is_palindrome(const int left, const int right) const {
    const int mid = (left + right - 1) / 2;
    return ((right - left) & 1 ? odd(mid) * 2 - 1 : even(mid) * 2)
           >= right - left;
  }

 private:
  std::vector<int> radius;
};

}  // namespace emthrm


#line 11 "test/string/manacher.test.cpp"

int main() {
  std::string s;
  std::cin >> s;
  const int n = s.length();
  emthrm::Manacher manacher(s);
  for (int i = 0; i < n; ++i) {
    std::cout << (manacher.odd(i) - 1) * 2 + 1;
    if (i + 1 == n) [[unlikely]] {
      std::cout << '\n';
    } else {
      std::cout << ' ' << manacher.even(i) * 2 << ' ';
    }
  }
  return 0;
}

Back to top page