# KMP算法

## 查找过程

`W`="ABCDABD"，`S`="ABC ABCDAB ABCDABCDABDE"为例说明查找过程。查找过程同时使用两个循环变量`m``i`

• `m`代表主文字符串`S`内匹配字符串`W`的当前查找位置，
• `i`代表匹配字符串`W`当前做比较的字符位置。

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

`W``S`的開頭比較起。比對到`S[3](=' ')`時，發現`W[3](='D')`與之不符。接著並不是從`S[1]`比較下去。已經知道`S[1]~S[3]`不與`W[0]`相合。因此，略過這些字元，令`m = 4`以及`i = 0`

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

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

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

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

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

## 部分匹配表

### 创建表算法示例

`W = "ABCDABD"`为例。以下将看到，部分匹配表的生成过程与前述查找过程大同小异，且出于类似原因是高效的。

 `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
```

### 建立表的算法的效率

• 在第一个分支里，`pos - cnd`不变，而`pos``cnd`同时自增，自然，`pos`增加了。
• 在第二个分支里，`cnd`被更小的`T[cnd]`所替代，从而增加了`pos - cnd`
• 在第三个分支里，`pos`增加了，而`cnd`不变，所以`pos``pos - cnd`都增加了。