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

• View this file on GitHub
• Last update: 2024-05-31 17:02:37+09:00
• Include: #include "src/string/Manacher.hpp"

• 参考実装：ei1333 (Luzhiled’s memo)

使い方

• vector<ll> manacher(string s)：文字列 $s$ の長さを $n$ として，長さ $n$ の整数列 $r$ を返す．$r[i]$ は $s[i]$ を中心とする回文半径で，$s[i - r[i]]$ から $s[i + r[i]]$ までが回文であることを表す．
• 文字と文字の間を中心とする回文半径も知りたいときは，両端を含めた境界 ($N + 1$ 個) に適当な文字 1 種類を挿入しておく．返される値は，挿入前の文字列における回文直径${} + 1$ (すなわち，極大な回文の長さ${} + 1$) になる．

$O(n)$ 時間

Verified with

• test/string/Manacher.test.cpp

Code

// 各位置での回文半径を求める
// aaabaaa -> 1214121
// 偶数長の回文を含めて直径を知るには，N+1 個の $ を挿入して 1 を引く
// $a$a$a$b$a$a$a$ -> 123432181234321
auto manacher(string s) {
   ll n = sz(s), i = 0, j = 0;
   vector<ll> r(n);
   while(i < n) {
      while(i >= j && i + j < n && s[i - j] == s[i + j]) j++;
      r[i] = j;
      ll k = 1;
      while(i >= k && i + k < n && k + r[i - k] < j) {
         r[i + k] = r[i - k];
         k++;
      }
      i += k, j -= k;
   }
   return r;
}

#line 1 "src/string/Manacher.hpp"
// 各位置での回文半径を求める
// aaabaaa -> 1214121
// 偶数長の回文を含めて直径を知るには，N+1 個の $ を挿入して 1 を引く
// $a$a$a$b$a$a$a$ -> 123432181234321
auto manacher(string s) {
   ll n = sz(s), i = 0, j = 0;
   vector<ll> r(n);
   while(i < n) {
      while(i >= j && i + j < n && s[i - j] == s[i + j]) j++;
      r[i] = j;
      ll k = 1;
      while(i >= k && i + k < n && k + r[i - k] < j) {
         r[i + k] = r[i - k];
         k++;
      }
      i += k, j -= k;
   }
   return r;
}

Back to top page