「部分マッチ」テーブル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/08 01:52 UTC 版)
「クヌース–モリス–プラット法」の記事における「「部分マッチ」テーブル」の解説
このテーブルの目的は S 内の各文字を複数回照合することを防ぐことである。線形検索の性質として、パターンの先頭とマッチする文字列に遭遇したとき、次の照合を開始すべき位置を与えることで複数回照合を防ぐことができる。換言すれば、パターン内を事前に検索して照合する必要のない文字数を各文字位置に対応して算出しておくのである。 ここで W の各文字位置で不一致が発生したとき、その直前の位置の文字列と W の先頭からの文字列が一致している場合、そのサブ文字列の長さのぶんだけバックトラックする。従って、T[i] の値は W の先頭からの文字列と W[i - 1]で完了する文字列が一致している長さに対応する。ここで空の文字列の長さを 0 とする。単語の先頭で不一致となる場合は特殊ケースであり（バックトラックできないため）、T[0] = -1 とする。
※この「「部分マッチ」テーブル」の解説は、「クヌース–モリス–プラット法」の解説の一部です。
「「部分マッチ」テーブル」を含む「クヌース–モリス–プラット法」の記事については、「クヌース–モリス–プラット法」の概要を参照ください。
ウィキペディア小見出し辞書の「「部分マッチ」テーブル」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 「部分マッチ」テーブルのページへのリンク
