Manacher algorithm
(Mylib/String/manacher.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• manacher(s)
  • 各位置iを中心とした最長奇数長回文の片側長さ(回文長Lに対してL/2+1)の配列を返す。

Requirements

Notes

Problems

References

Verified with

• test/yosupo-judge/enumerate_palindromes/main.manacher.test.cpp

Code

#pragma once
#include <optional>
#include <vector>

namespace haar_lib {
  template <typename Container>
  std::vector<int> manacher(const Container &s) {
    const int n = s.size();
    std::vector<int> ret(n);
    int center = 0;

    for (int cur = 0; cur < n; ++cur) {
      int left = center - (cur - center);

      if (left >= 0 and cur + ret[left] < center + ret[center]) {
        ret[cur] = ret[left];
      } else {
        int len = center + ret[center] - cur;
        while (cur - len >= 0 and cur + len < n and s[cur - len] == s[cur + len]) ++len;
        ret[cur] = len;
        center   = cur;
      }
    }

    return ret;
  }

  template <typename Container>
  std::vector<int> manacher_all(const Container &s) {
    using T     = typename Container::value_type;
    const int N = s.size();
    std::vector<int> ret(2 * N - 1);

    {
      auto res = manacher(s);
      for (int i = 0; i < N; ++i) {
        ret[i * 2] = res[i] * 2 - 1;
      }
    }

    {
      std::vector<std::optional<T>> T;
      for (int i = 0; i < N; ++i) {
        if (i) T.push_back(std::nullopt);
        T.push_back(s[i]);
      }

      auto res = manacher(T);
      for (int i = 0; i < N - 1; ++i) {
        ret[i * 2 + 1] = (res[i * 2 + 1] / 2) * 2;
      }
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/String/manacher.cpp"
#include <optional>
#include <vector>

namespace haar_lib {
  template <typename Container>
  std::vector<int> manacher(const Container &s) {
    const int n = s.size();
    std::vector<int> ret(n);
    int center = 0;

    for (int cur = 0; cur < n; ++cur) {
      int left = center - (cur - center);

      if (left >= 0 and cur + ret[left] < center + ret[center]) {
        ret[cur] = ret[left];
      } else {
        int len = center + ret[center] - cur;
        while (cur - len >= 0 and cur + len < n and s[cur - len] == s[cur + len]) ++len;
        ret[cur] = len;
        center   = cur;
      }
    }

    return ret;
  }

  template <typename Container>
  std::vector<int> manacher_all(const Container &s) {
    using T     = typename Container::value_type;
    const int N = s.size();
    std::vector<int> ret(2 * N - 1);

    {
      auto res = manacher(s);
      for (int i = 0; i < N; ++i) {
        ret[i * 2] = res[i] * 2 - 1;
      }
    }

    {
      std::vector<std::optional<T>> T;
      for (int i = 0; i < N; ++i) {
        if (i) T.push_back(std::nullopt);
        T.push_back(s[i]);
      }

      auto res = manacher(T);
      for (int i = 0; i < N - 1; ++i) {
        ret[i * 2 + 1] = (res[i * 2 + 1] / 2) * 2;
      }
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page