引用Wiki的一段话
在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。
本文符号表
S: 主字符串，即待查找的字符串W: 子字符串，即从S中查找的字符串i: 主字符串的index，即当前查找的位置j: 子字符串的index，即当前匹配的位置
介绍KMP之前我们需要了解一下字符串匹配的算法Brute-Force, 暴力匹配。
Brute-Force(BF)
顾名思义，暴力匹配是W与字符串S的每一个与W长度相同的子串的匹配。
动画演示
TODO
时间复杂度
O( len(W) * len(S) )
KMP
由BF算法的动画中可以看出，每一轮的匹配都是从i+1,j=0开始的，这样就不能利用之前的匹配失败结果，而KMP算法利用了之前的匹配失败结果，从而减少了匹配次数。
动画演示
TODO
Golang实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
func strStr(haystack string, needle string) int {
// KMP算法
pmt := partialMatchTable(needle)
i, j := 0, 0
for i < len(haystack) && j < len(pmt) {
if haystack[i] == needle[j] {
j++
i++
} else {
if j == 0 {
i++
} else {
j = pmt[j-1]
}
}
}
if i == len(haystack) && j < len(pmt) {
return -1
}
return i - len(pmt)
}
func partialMatchTable(needel string) []int {
lenPmt := len(needel)
pmt := make([]int, lenPmt)
for i, j := 1, 0; i < lenPmt; {
if needel[i] == needel[j] {
j++
pmt[i] = j
i++
} else {
if j == 0 {
pmt[i] = j
i++
} else {
j = pmt[j-1]
}
}
}
return pmt
}
|