ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ 概要 Mancher のアルゴリズムは与えられた長さ $n$ の文字列 $s$ に対して、各文字の回文半径（その文字を中心とした回文の長さ引く $1$ 割る $2$）を計算するアルゴリズムです。これの出力要件とアルゴリズムを少し変えることで、実装の複雑さはほとんど変わらず、より使いやすいものにすることができます。 方針 各 $i$（$0 \le i \le 2n$）に対して、$l + r = i$ を満たす最大の回文区間 $[l, r[ \subseteq [0, n[$ の長さ $r - l$ を $A _ i$ と定め、これを計算することにしましょう。こうすると偶数長回文に対応しやすいです… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2024%2F03%2F17%2F034026" title="Manacher&#39;s algorithm でダミー文字を使わなくて済む方法 - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20240530/20240530203622.png Hatena Blog https://hatena.blog 2024-03-17 03:40:26 rich https://blog.ngtkana.com/entry/2024/03/17/034026 1.0 100%