potetisensei https://blog.hatena.ne.jp/potetisensei/ 生きたい https://potetisensei.hatenablog.com/ 大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。 MP法 MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場しない。 MP法では、パターン文字列に対してborderと呼ばれる値を計算することにより、シフト量を定める。 ある文字列Sのborderとは、Sの部分文字列であって、Sの接頭辞かつ接尾辞であるような文字列Wのことである。 MP法では、i=0..|S|に対して、S[0:i-1]の最長border(の長さ)をO(|S|)で求め、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpotetisensei.hatenablog.com%2Fentry%2F2017%2F07%2F10%2F174908" title="MP法とKMP法の違い - 生きたい" 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 2017-07-10 17:49:08 rich https://potetisensei.hatenablog.com/entry/2017/07/10/174908 1.0 100%