betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 H - 根室の巫女 解法 Morris-Pratt法について まず、公式解説（？）にも書いてあるMorris-Pratt法（MP）について触れておきます。私も実戦で使ったことはないのですが…ある長さ の文字列 があったときに、全ての に対して以下の値を求めた数列 を求めるアルゴリズムです。 の先頭 文字だけからなる文字列を とする。 未満の整数 であって、「 の先頭 文字と末尾 文字が一致する。」という条件を満たす の最大値を とする。 としてしまうと先頭 文字と末尾 文字は当然一致してしまうので、それ以外で最大のものを求めることに注意してください。 この数列は文字列検索を高速に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F05%2F25%2F105345" title="いろはちゃんコンテスト Day2 H - 根室の巫女 - ARMERIA" 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/b/betrue12/20190525/20190525104911.png Hatena Blog https://hatena.blog 2019-05-25 10:53:45 rich https://betrue12.hateblo.jp/entry/2019/05/25/105345 1.0 100%