京都大学 情報学研究科 知能情報学専攻 2019年8月実施 情報学基礎 F2-2

Author

祭音Myyura

Description

文字のテキスト文字列 (text) の先頭から順に、 文字のパターン (pattern) を探す問題を考える。

例えば、図 (a) のように、text の位置 から始まる文字列と pattern "ABCA" を比較し、３文字目が不一致であったとする。 このとき、あらかじめ pattern の性質を調べておけば、pattern を１つ右にずらしても照合することはなく、pattern を２つ右にずらして、text の位置 から比較すれば良いことがわかる。 一方、図 (b) のように、４文字目で不一致であった場合には、pattern を４つ右にずらして、text の位置 と pattern の先頭の比較から再開すれば良い。

(1) pattern の位置 で照合が失敗したとき、pattern を最大何文字まで右にずらせるかを で表すこととする。 図 (a) では 、図 (b) では である。 次の pattern について、 の値を求めよ。

• (i) AAAB
• (ii) ABAC

(2) (1) の pattern (ii) と text "ABABBAABACA" との照合の過程を図示せよ。 pattern と text のどの文字が比較されて行くかを明示すること。

(3) このアルゴリズムの時間計算量を示せ。また、このアルゴリズムにおける比較の最大回数と、その具体例 (pattern と text) を示せ。

Kai

(1)

(i)

(ii)

(2)

ABABBAABACA
ABAC
  ABAC
     ABAC
      ABAC

(3) - send help

このアルゴリズムはクヌース–モリス–プラット法（KMP法と略記）と呼ばれる文字列検索アルゴリズムの一種である。

計算量は であり、証明は Wiki を参考すれば良い。

最悪の pattern と text の例：

• pattern: AAAAA
• text: AAAABAAAABAAAABAAAAA