テーブル生成法の擬似コードと解説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「テーブル生成法の擬似コードと解説」の解説
上述の実施例はテーブル生成の一般的な技術を説明している。基本的にそれが全てである。ある位置に到達したとき、すべきことは既に完了している。複雑化させる小さな問題は先頭で間違ってサブ文字列を与えてしまうことである。これに対処するにはちょっとした初期化コードが必要となる。 algorithm kmp_table: input: an array of characters, W (解析すべき単語) an array of integers, T (生成すべきテーブル) output: nothing (ただし、処理を行うことでテーブルの中身が書き込まれる) define variables: an integer, i ← 2 (T の中で現在計算している位置) an integer, j ← 0 (現在見ているサブ文字列の次の文字のインデックス。0から始まる) (先頭ふたつの値は固定。ただしアルゴリズムの実装によっては具体的値は異なる) let T[0] ← -1, T[1] ← 0 while i is less than the length of W, do: (第一の場合: サブ文字列は継続中) if W[i - 1] = W[j], let T[i] ← j + 1, i ← i + 1, j ← j + 1 (第二の場合: サブ文字列は継続しないが、フォールバック可能) otherwise, if j > 0, let j ← T[j] (第三の場合: 対象をはみ出した。このとき j = 0) otherwise, let T[i] ← 0, i ← i + 1
※この「テーブル生成法の擬似コードと解説」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「テーブル生成法の擬似コードと解説」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
- テーブル生成法の擬似コードと解説のページへのリンク
