記号の定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 16:30 UTC 版)
「ボイヤー-ムーア文字列検索アルゴリズム」の記事における「記号の定義」の解説
A N P A N M A N - P A N - - - - - - - P A N - - - - - - - P A N - - - - - - - P A N - - - - - - - P A N - - - - - - - P A N - テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。 文字列 S に対する操作を以下のように表す： S[i]： 文字列 S の i 番目の文字 S[i..j]： 文字列 S の i から j 番目までの部分文字列（i 文字目、j 文字目をそれぞれ含む） 文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。 len(S)：S の長さ S[1..i], 1 ≤ i ≤ len(S)：S のプレフィックス S[i..len(S)], 1 ≤ i ≤ len(S)：S のサフィックス 検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T 上での P の位置を T の先頭から数えた P の末尾の文字の位置と定義し、k で表す。 T：テキスト（被検索文字列） P：パターン（検索文字列） k：テキスト T 上でのパターン P の最後の文字の位置（len(P) ≤ k ≤ len(T)） 「P が T に一致する」とは P と文字列として等価な部分文字列 T[i..j] が存在することをいう。より具体的に、P が位置 k で T と一致するとは、k 番目から前方 len(P) 文字分を取り出した部分文字列 T[(k − len(P) + 1)..k] が P と文字列として等価であることをいう。 本項では特に断りない限り、m を len(T), n を len(P) の意味で使う。
※この「記号の定義」の解説は、「ボイヤー-ムーア文字列検索アルゴリズム」の解説の一部です。
「記号の定義」を含む「ボイヤー-ムーア文字列検索アルゴリズム」の記事については、「ボイヤー-ムーア文字列検索アルゴリズム」の概要を参照ください。
- 記号の定義のページへのリンク
