hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://codeforces.com/contest/1326/problem/D2 前提知識 Manacher 解説 https://codeforces.com/contest/1326/submission/73898734 高速にクエリをさばいていこう。 文字列のprefixとsuffixで回文となる最大長を計算しておく。 この最大長以下であれば、どれも回文となる。 prefix+回文+suffixで回文になるように、真ん中の回文を全探索しよう。 manacherを使えば、中心からの回文の長さが分かる。 これを使おう。 ある中央から、なるべく長い回文を選んだ時に、最大のpref… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F03%2F22%2F001248" title="Prefix-Suffix Palindrome (Hard version) [Codeforces Global Round 7 D2] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-03-22 00:12:48 rich https://blog.hamayanhamayan.com/entry/2020/03/22/001248 1.0 100%