この検索アルゴリズムの擬似コードと解説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「この検索アルゴリズムの擬似コードと解説」の解説
前述の実施例はこのアルゴリズムのあらゆる要素を含んでいる。ここで、現在の照合が不一致に終わった際に次の照合の開始時点で参照する「部分マッチ」テーブル T を使用するものとする（後述）。T のエントリは、S[m] から照合して S[m + i] と W[i] が不一致となった際に次に照合を開始すべき位置を S の m + i - T[i] 番目とするよう設定される（つまり、T[i] は不一致の際のバックトラッキングを示す）。これには2つの意味がある。第一に T[0] = -1 は W[0] が不一致の場合にバックトラックできず単に次の文字を照合すべきであることを示す。第二に m + i - T[i] が次の照合のインデックスとなるが、その先頭 T[i] 個の文字を照合する必要はなく、照合は W[T[i]] からでよい。以下の擬似コードは KMP法の実装例である。 algorithm kmp_search: input: an array of characters, S (検索対象のテキスト) an array of characters, W (単語) output: an integer (W が見つかった際の S 内の位置。ただし先頭文字は 0番目とする) define variables: an integer, m ← 0 (S 内の現在照合中の開始位置) an integer, i ← 0 (W 内の現在位置) an array of integers, T (テーブル。他で事前に構築される) while m + i is less than the length of S, do: if W[i] = S[m + i], let i ← i + 1 if i equals the length of W, return m otherwise, let m ← m + i - T[i], and if i > 0, let i ← T[i] (W が S 内に見つからなかった場合) return the length of S
※この「この検索アルゴリズムの擬似コードと解説」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「この検索アルゴリズムの擬似コードと解説」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
- この検索アルゴリズムの擬似コードと解説のページへのリンク
