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

标签：

• Kyoto-University
• Knuth-Morris-Pratt-Algorithm
• Knuth-Morris-Pratt-Failure-and-Shift-Table
• Algorithm-Complexity

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) を示せ。

题目描述

考虑在长度为 $n$ 的文本串中从头查找长度为 $m$ 的模式串。若预先分析模式自身结构，在位置 $j$ 失配时可以跳过不可能匹配的起点。题图以模式 ABCA 说明：第 3 个字符失配时可右移 2 位，第 4 个字符失配时可右移 4 位。

以 $\operatorname{shift}[j]$ 表示在模式位置 $j$ 失配时最多可安全右移的字符数。

1. 对下列模式分别求 $\operatorname{shift}[j]$（$1\le j\le4$）：
   1. AAAB；
   2. ABAC。
2. 图示模式 ABAC 与文本 ABABBAABACA 的完整匹配过程，明确标出依次比较的模式字符与文本字符。
3. 给出该算法的时间复杂度，并给出最大比较次数以及达到该次数的具体模式串、文本串例子。

Kai

(1)

(i)

$$\text{shift}[1] = 1, \ \text{shift}[2] = 2, \ \text{shift}[3] = 3, \ \text{shift}[4] = 1$$

(ii)

$$\text{shift}[1] = 1, \ \text{shift}[2] = 1, \ \text{shift}[3] = 3, \ \text{shift}[4] = 2$$

(2)

ABABBAABACA
ABAC
  ABAC
     ABAC
      ABAC

比較する $(\text{text の位置},\text{pattern の位置})$ は順に

$$(1,1),(2,2),(3,3),(4,4),(4,2),(5,3), (6,1),(7,2),(7,1),(8,2),(9,3),(10,4)$$

であり，text の位置 $7$ から ABAC が見つかる。

(3)

以下では $1\le m\le n$ とし、残りの text が pattern より短くなった時点で終了する。$m>n$ なら文字比較をせずに不一致と判定できる。 $\text{shift}$ 表は $O(m)$ 時間で構成できる。照合中，一致した比較は text の位置を1つ進め，不一致の比較は pattern の開始位置を1つ以上進める。$m\ge2$ のとき，照合に成功する場合は一致比較が高々 $n$ 回，不一致比較が高々 $n-m$ 回である。照合に失敗する場合はそれぞれ高々 $n-1$ 回，$n-m+1$ 回である。いずれも合計は

$$n+(n-m),\qquad (n-1)+(n-m+1)$$

以下であるから，最大比較回数は $2n-m$ である。よって計算量は $O(m+n)$ である。

$\text{pattern}=A^{m-1}B, \text{text}=A^n$ では，最初に $m$ 回，以後の各開始位置で2回ずつ比較するため，

$$m+2(n-m)=2n-m$$

回となり上界を達成する。（$m=1$ の最大回数は $n$。）