KMP 算法很复杂,有很多解释方式( DFA,前缀后缀),下面是我的一种理解。
我们在 s1 中匹配 s2,s1、s2 的长度分别为 N,M 1,首先我们按顺序匹配,直到匹配失败
i 表示 s1 的匹配起始位置,j 表示 s2 的匹配位置
2,如果使用暴力搜索算法下一步将是这样的:
这样算法的复杂度是N*M
但是我们可以利用已经匹配到的字符串( AABAA )进行优化:
这种情况一共有以下几种:
4,这里的 C 其实就是 AABAA 的最长前缀后缀匹配
它满足:
1,C 是一个前缀后缀匹配:AABAA 的长度为 n 前缀和长度为 n 的后缀相等
2,C 是 n 最大的前缀后缀匹配
接下来要做的事情就是:
i+=(j-2)=3
j=2
而 i+j=5,所以当前匹配位置维持在红框处不变
6,所以只要我们计算出 s2 上面每个位置的最长前缀后缀匹配长度(前后缀匹配数组)就可以加速匹配过程了
更详细的分析可以看出 KMP 算法的匹配过程时间复杂度是 O(N)的
下面介绍如何计算前后缀匹配数组 preSuffixArr
1,首先 preSuffixArr[0]=0, 这是因为前后缀匹配不能匹配自己
2,然后 preSuffixArr[n]可以按照下面的规则递归计算:
首先取 v=preSuffixArr[n-1],代表前 n-1 个字符的最长前后缀匹配:
如果 s2[v+1]==s2[n], 那么可以补上这个字符,构成一个长度为 n+1 的最长前后缀匹配
如果 s2[v+1]!=s2[n], 继续对 v=preSuffixArr[v-1]计算这个过程
下面示例介绍如何构造 AACAABAAA 的[前后缀匹配数组 preSuffixArr]
k 表示当前计算位置,
1,k=0,preSuffixArr[0]=0
2,k=1,然后由于 s2[0]==s2[1]="A",preSuffixArr[1]=preSuffixArr[0]+1
3,k=2,v=preSuffixArr[1]=1, 由于 s2[2]!=s2[1],匹配失败
然后 v=preSuffixArr[v-1]=0, s2[2]!=s2[0], 匹配失败 preSuffixArr[2]=0
...
9,k=8,v=preSuffixArr[7]=2,s2[2]!=s2[8],匹配失败
v=preSuffixArr[7]=2,s2[1]!==s2[8],匹配成功
可以证明计算前后缀匹配数组的过程时间复杂度是 O(M)的,KMP 算法整体时间复杂度是 O(M+N)
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.