京都大学 情報学研究科 知能情報学専攻 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. 给出该算法的时间复杂度，并给出最大比较次数以及达到该次数的具体模式串、文本串例子。

考点

• KMP 失配/移位表：根据已匹配前缀的最长真前后缀计算失配后的安全位移。
• 字符串匹配过程模拟：按移位表逐次跟踪比较位置，不回退已经排除的文本起点。
• 算法复杂度与最坏构造：分析预处理和搜索阶段的比较次数，并构造重复字符模式达到上界。

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

(3) - send help

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

計算量は $O(m+n)$ であり、証明は Wiki を参考すれば良い。

最悪の pattern と text の例：

• pattern: AAAAA
• text: AAAABAAAABAAAABAAAAA