KMP算法如果理解原理的话,其实很简单。
这里根据自己的理解简单介绍下。
KMP算法的名称由三位发明者(Knuth、Morris、Pratt)的首字母组成,又称字符串查找算法。
个人觉得可以理解为最小回溯算法,即匹配失效的时候,尽量少回溯,从而缩短时间复杂度。
KMP算法有两个关键的地方,1)求解next数组,2)利用next数组进行最小回溯。
next数组的取值只与模式串有关,next数组用于失配时回溯使用。
在简单版本的KMP算法中,每个位置 j 的 next 值表示的是模式串的最长前缀的最后一个字符的位置(假设为 k ),其中最长前缀(长度为 k+1 )需要与模式串截至当前位置长度亦为 k+1 的后缀匹配,且 k 最大为 j-1 ,否则相当于没有回溯。当k=-1的时候,表示找不到这样的最长前缀。
用公式表示为
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVP9EVY4RWbixmWXpVMoNjYox2RjZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zM1QDOxYTNwITMzUDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
当k=-1的时候,表示空串。p表示模式串。
下面举一个计算next数组的例子,假设模式串是 “ abaabcaba ” 。
j
1
2
3
4
5
6
7
8
p
a
b
c
next[j]
-1
以 j = 8 为例,最长前缀为aba,最后一个字符位置为2,故 next[8] = 2 。
那么如何快速求解next数组呢?
这里有点动态规划的思想在里面,其中位置 j 等于 0 的 next 值为-1,表示找不到这样的最长前缀。 j > 0 时,next值可以通过 j - 1 位置的next值求得。
求解next[ j ]的步骤:
t = next[ j - 1 ] + 1,t 指向可能等于 p[ j ] 的位置,即 p[ t ] 可能等于 p[ j ]。
如果 p[ t ] = p[ j ] , 那么 next[ j ] = next[ j - 1 ] + 1
如果 p[ t ] != p[ j ] , 则令 t = next[ t - 1 ] + 1,继续第 2 步直到 t = 0 或者找到位置。
结束时判断p[ t ] 是否等于 p[ j ] ,如果等于则 next[ j ] = t , 否则等于 -1 。
下图表示了第一次不匹配,第二次匹配的过程,其它过程可以类推。其中 或 覆盖部分表示最长匹配串。 为待判定位置,
为已判定位置。
0123 j
×××××××××××××××××××××××××××××××××××××××××
s ××××××××××××××××××××××××××××××××××××××××××××
p ××××××××××××××
在j处不失配时,前面的有部分匹配,这时需要利用next数组信息进行最小回溯。
(这里 i 指向 s , j 指向 p。)
注意在 j = 0 的时候失配时,直接 i++ 即可。
当 j > 0 的时候,需要利用next数组最快找到 p[ j ] == s[ i ] 的位置。
如果 j 移动到了0还找不到,则 i++,然后继续匹配。
这里我们可以发现只有 j 回溯了,i没有回溯,但是由于普通版本的 KMP 算法 j 需要不停地回溯直到找到合适的回溯位置,因此速度不是特别快,还可以继续优化,感兴趣的读者可以想想如何事先求解好next数组从而不需要不停地回溯。
strStr返回的是首次匹配的地址,如果不能匹配则返回NULL。
由于有人问有没有java版本的,由于鄙人java比较挫,写java时部分还写成了scala的语法,不知道代码是否规范,有优化的地方还麻烦java方面的大神指点。