京都大学 情報学研究科 知能情報学専攻 2019年8月実施 情報学基礎 F2-2
Author
祭音Myyura
Description
\(n\) 文字のテキスト文字列 (text) の先頭から順に、\(m\) 文字のパターン (pattern) を探す問題を考える。
例えば、図 (a) のように、text の位置 \(i\) から始まる文字列と pattern "ABCA" を比較し、３文字目が不一致であったとする。 このとき、あらかじめ pattern の性質を調べておけば、pattern を１つ右にずらしても照合することはなく、pattern を２つ右にずらして、text の位置 \(i+2\) から比較すれば良いことがわかる。 一方、図 (b) のように、４文字目で不一致であった場合には、pattern を４つ右にずらして、text の位置 \(i+4\) と pattern の先頭の比較から再開すれば良い。
(1) pattern の位置 \(j\) で照合が失敗したとき、pattern を最大何文字まで右にずらせるかを \(\text{shift}[j]\) で表すこととする。 図 (a) では \(\text{shift}[3]=2\)、図 (b) では \(\text{shift}[4]=4\) である。 次の pattern について、\(\text{shift}[j] \ (1 \leq j \leq 4)\) の値を求めよ。
- (i) AAAB
- (ii) ABAC
(2) (1) の pattern (ii) と text "ABABBAABACA" との照合の過程を図示せよ。 pattern と text のどの文字が比較されて行くかを明示すること。
(3) このアルゴリズムの時間計算量を示せ。また、このアルゴリズムにおける比較の最大回数と、その具体例 (pattern と text) を示せ。
Kai
(1)
(i)
(ii)
(2)
(3) - send help
このアルゴリズムはクヌース–モリス–プラット法（KMP法と略記）と呼ばれる文字列検索アルゴリズムの一種である。
計算量は \(O(m+n)\) であり、証明は Wiki を参考すれば良い。
最悪の pattern と text の例：
- pattern: AAAAA
- text: AAAABAAAABAAAABAAAAA