字符串匹配：KMP 算法
解析BF 算法问题预先处理再次改进
Python 代码C 代码
后记
字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上。
模式串匹配算法发展得比较慢，实用的出现很晚。KMP 算法是大部分书介绍完 BF 算法后的简化方法，说容易也是说难也行，其实理解了真的很容易操作。
解析
KMP 算法利用的是模式串本身的性质，与文本串无关，这点一定要记住。如果模式串中存在相似部分，比如 abcabdabe，abc、abd 和 abe 三部分都很相似，KMP 算法利用这个特点提高匹配效率。
BF 算法问题
串匹配时某个位置不匹配时，需要移动指针重新匹配。BF 算法的问题就在于匹配失败时文本串只前进一位，而模式串回到开头匹配，造成不必要的浪费。比如下面情况： 如果是 BF 算法，下一轮操作，是不是很傻： 既然 ab 和 ac 有相似部分 a，如果 ac 的 a 不能匹配，那么 ab 的 a 也必然不能和文本串这个位置匹配，可以直接跳过： 同时，如果 ac 的 c 匹配失败，有没有可能这个位置是 ab 呢： 是不是很快了呢？一下跳跃那么多。所以问题在于要移动多少。
预先处理
针对模式串每个位置匹配失败的移动距离，需要一个额外的数组记录，就叫 next 数组。设模式串长度 m，数组长度即为 m。在开始匹配前，进行模式串处理，找最长相似真前缀和真后缀。 对于 abcabdabe 这个串，next 数组如图。next[0]=-1 是固定操作，第一位置匹配失败肯定要移动文本串位置。对于 ab、abc、abca 三部分，没有相似成分，所以匹配失败了直接从头再来；abcab 出现了相似成分 a*，如果第二处 a* 匹配失败则利用第一处 a* 尝试匹配；abcabd 有相同成分 ab* 所以后面的 ab* 匹配失败则尝试前面的 ab* 匹配… 总结为一张表如上，注意相似真前后缀长度放在的是 next 数组下一个位置，因为要比较的是相似部分后面的不同部分。 具体到计算方法：用两个指针，设为 i 和 j，初始 i=0、j=-1。next[0]=-1，每个位置的 next 值与前一位有关，要么0要么前一位 +1；当指针指向字符相同时两个指针都自增，并且 next 的值自增并放到下一位置；如果不同 j 回溯，回溯到的位置是 next 的值，如果 j 为 -1 就同时自增。
再次改进
虽然计算 next 数组然后快速移动提高了效率，但还不够。考虑一种极端的情况 aaaaaab，正常来说 next 是 [-1, 0, 1, 2, 3, 4, 5]，但前面的一串 a 有一个匹配失败其实都可以跳过全部 a；比如上面的串 abcabdabe，后面两个 ab 匹配 b 失败都会尝试和第一个 ab 的 b 匹配，因为符合 a*，显然还可以加速。那么计算 next 数组时多一个条件：指针自增后如果字符相同就再回溯，如果不同则按原来操作。比如 abcab… 时指针分别指到两个 a，自增后发现两个 b 也是相同字符，让后一个 b 的回溯位置和前一个 b 的回溯位置相同。 看代码会更容易理解。
Python 代码
def kmp_match(text
, pat
):
next = get_next
(pat
)
a
= 0
b
= 0
while a
< text
.__len__
() and b
< pat
.__len__
():
if b
== -1 or text
[a
] == pat
[b
]:
a
+= 1
b
+= 1
else:
b
= next[b
]
if b
== pat
.__len__
():
print("found:", a
-b
)
a
= a
-b
b
= -1
"""
未改进的 next
def get_next(pat):
next = [-1, ]
a = -1
b = 0
while b < pat.__len__()-1:
if a == -1 or pat[a] == pat[b]:
a += 1
b += 1
next.append(a)
else:
a = next[a]
return next
"""
def get_next(pat
):
next = [-1, ]
j
= -1
i
= 0
while i
< pat
.__len__
()-1:
if j
== -1 or pat
[j
] == pat
[i
]:
j
+= 1
i
+= 1
if pat
[j
] != pat
[i
]:
next.append
(j
)
else:
next.append
(next[j
])
else:
j
= next[j
]
return next
kmp_match
(input(), input())
C 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void getNext(short* next
, char* pat
);
int main(int argc
, const char * argv
[])
{
char* text
= "aaaggavvabcabbabc", * pat
= "abbabc";
short* next
= malloc(strlen(pat
) * sizeof(short));
next
[0] = -1;
getNext(next
, pat
);
short i
= 0, j
= 0;
printf("%lu %lu", strlen(text
), strlen(pat
));
while (i
< (int)strlen(text
) && j
< (int)strlen(pat
))
{
if (j
== -1 || *(text
+i
) == *(pat
+j
))
i
++, j
++;
else
j
= next
[j
];
if (j
== strlen(pat
))
{
printf("found at: %d", i
-j
);
i
= i
-j
;
j
= -1;
}
}
free(next
);
return 0;
}
void getNext(short* next
, char* pat
)
{
short i
= 0, j
= -1;
while (i
< strlen(pat
)-1)
{
if (j
== -1 || *(pat
+i
) == *(pat
+j
))
{
i
++, j
++;
if (*(pat
+i
) == *(pat
+j
))
next
[i
] = j
;
else
next
[i
] = next
[j
];
}
else
j
= next
[j
];
}
}
后记
严格的数学证明没写，不难懂但有点抽象，第一次看是会看不懂。这个算法看懂前和看懂后是两种感觉，所以需要点时间理解。本篇写得一般，实在不知道怎么解释最清晰。 其实 KMP 算法用于串匹配不太常见，它比较适合无序又有规律的串。比如在网页搜索 tomorrow，这词没有一处可以 KMP…
