そのうち誰かの役に立つ

もしくは誰の役にも立たない

Knuth-Morris-Pratt法(KMP法)

アルゴリズムとデータ構造 KMP法 Python3 Go

概要

  • 記号列 S = \lbrack s_{0}, \dots, s_{N - 1} \rbrack とパターン P = \lbrack p_{0}, \dots, p_{M - 1} \rbrack が与えられたとき、 P と一致する S の部分列を探してその位置を返す
  • 部分一致テーブル \mathit{PMT} を事前に計算しておくことで、不一致となったときに次の探索を先頭からではなく途中までは既に部分一致したものとして一部スキップできる（場合がある）
  • 部分一致テーブルは下記のように構成された長さ M + 1 の配列である
    • \mathit{PMT}\lbrack 0 \rbrack = -1, \mathit{PMT}\lbrack 1 \rbrack = 0
    • i = 2, j = 0 を初期値として、 i \le M である間以下の操作をする
      $$ \begin{array}{} \mathit{PMT} \lbrack i \rbrack = j + 1, i = i + 1, j = j + 1 & \mathrm{if}\; P \lbrack i - 1 \rbrack = P \lbrack j \rbrack \\ j = \mathit{PMT} \lbrack i \rbrack & \mathrm{else}\; \mathrm{if}\; 0 \lt \mathit{PMT} \lbrack i \rbrack \\ \mathit{PMT} \lbrack i \rbrack = 0, i = i + 1 & \mathrm{else} \end{array} $$
  • 計算時間は部分一致テーブルの構築に O(M) 、探索に O(N)

実装

  • 入力の型は自由
    • サンプル入力では整数列とする
  • パターン一致する部分列の先頭位置をすべて返す

Python3で実装する

Powered by OnlineGDB

Goで実装する

interface型のまま一致判定ができるため、入力をinterface型にキャストすることで自由にできた