JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ Manacher法 回文 アルゴリズム学習 基礎から徹底 直近のABCで出題された ABC398 F - ABCBA が、「文字列中の各文字、あるいは隣接2文字どうしの隙間を中心と考えた場合において作成可能な最大の回文長」を高速に求められればそれだけで片付く問題というのはすぐに分かったが肝心のアルゴリズムをどうすればいいのかを把握していなかったせいで敗北に終わり途轍もなく悔しいため、今回でしっかりと固めておく。 ※特に断らない限り、本記事の記載は0-indexedを前提とする。 １）愚直な方針 ある文字列\(S\)について考える時、その先頭と末尾、および隣接2文字の間に対し、\(S\)中に一度も現れないような特定の一文字（以下ダミー文字と呼ぶ）を付加… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F03%2F29%2F051434" title="Manacher法により回文の最大長を求める話の勉強 - JunKobayashi&#39;s Diary" 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/J/JunKobayashi/20250329/20250329050734.png Hatena Blog https://hatena.blog 2025-03-29 05:14:34 rich https://junkobayashi.hatenablog.com/entry/2025/03/29/051434 1.0 100%