string/manacher.hpp

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "string/manacher.hpp"

Verified with

• test/yosupo/String/Enumrate-Palindromes.test.cpp

Code

vector<int> manacher(const string &s){
  const int len = s.size();
  vector<int> r(len);
  int i = 0, j = 0;
  while(i < len){
    while(i-j >= 0 && i+j < len && s[i-j] == s[i+j]) j++;
    r[i] = j;
    int k = 1;
    while(i-k >= 0 && k+r[i-k] < j) r[i+k] = r[i-k], k++;
    i += k; j -= k;
  }
  return r;
}

#line 1 "string/manacher.hpp"
vector<int> manacher(const string &s){
  const int len = s.size();
  vector<int> r(len);
  int i = 0, j = 0;
  while(i < len){
    while(i-j >= 0 && i+j < len && s[i-j] == s[i+j]) j++;
    r[i] = j;
    int k = 1;
    while(i-k >= 0 && k+r[i-k] < j) r[i+k] = r[i-k], k++;
    i += k; j -= k;
  }
  return r;
}

Back to top page