0%

对KMP算法的一些理解

KMP算法是一种字符串匹配算法,可以在O(n+m)时间复杂度内实现两个字符串的匹配。

关于字符串匹配

暴力解决字符串匹配即通过两个串的每个字符逐一比较,python实现如下:

1
2
3
4
def match(S, P):
for i in range(len(S) - len(P) + 1):
if S[i:i+len(P)] == P:
return i

如果 n = len(S), m = len(P)。那么最坏的情况下,暴力解法的时间复杂度能去到O(nm)。

暴力解法并没有利用字符串匹配过程中残留的一部分信息,而KMP算法则是通过“尽可能减少比较的趟数”来做到优化,即看看能否在匹配失败后,跳过一部分不可能成功的字符串比较来使复杂度降低。

简述KMP起始思路