# 克努斯-莫里斯-普拉特算法

## 算法说明

### 查找算法实例

```m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
```

```m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456
```

```m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456
```

`m = 10, i = 2`的地方，又出現不相符的情況。類似地，令 `m = 11, i = 0`繼續比較：

```m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456
```

```m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456
```

## “部分匹配”表（又叫做“失配函数”）

### 建立表算法示例

 `i` `W[i]` `T[i]` 0 1 2 3 4 5 6 A B C D A B D -1 0 0 0 0 1 2

 `i` `W[i]` `T[i]` 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 P A R T I C I P A T E I N P A R A C H U T E -1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 3 0 0 0 0 0

### 建立表算法的伪代码的解释

```algorithm kmp_table:
input:
an array of characters, W (the word to be analyzed)
an array of integers, T (the table to be filled)
output:
nothing (but during operation, it populates the table)

define variables:
an integer, pos ← 2 (the current position we are computing in T)
an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)

(the first few values are fixed but different from what the algorithm might suggest)
let T[0] ← -1, T[1] ← 0

while pos < length(W) do
(first case: the substring continues)
if W[pos - 1] = W[cnd] then
let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

(second case: it doesn't, but we can fall back)
else if cnd > 0 then
let cnd ← T[cnd]

(third case: we have run out of candidates.  Note cnd = 0)
else
let T[pos] ← 0, pos ← pos + 1
```