之前学过kmp算法,但都是马马虎虎,没有深入理解,最近因为算法题重刷了网课,在博客里做下笔记,加深理解。

1. KMP为什么能优化?

按照往常思维,运用普通算法所得的最坏复杂度是O(mn),m为目标串长度,n为模式串长度,对目标串的每个字符向模式串一一匹配,最坏每个字符都匹配n次。

KMP的核心思想是递归寻找字符串的最大公共前后缀,即失败函数的计算,通过失败函数寻找相同的前后缀进行跳转,举个例子,模式串abcegabg,失败函数可得为 -1,-1,-1,-1,-1,0,1,-1;abcega末尾的a,对应的数字0表示在abcega中,有最大公共前后缀a,abcegab同理则为最大公共前后缀ab,abcdgabg则表示无公共前后缀。

可得match[ j ]的定义:match[ j ]为满足p0 p1…pi=pj-i…pj 的最大i值,即是最大公共前后缀的前缀位置否则为0

按照失败函数的计算,我们可以在匹配失败后迅速跳转,从而大量减少时间消耗在模式串的匹配上,最坏时间复杂度为O(m+n)。

计算失败函数过程不再赘述,一个巧妙的随着长度增加不断求自身最大公共前后缀的过程。RT

2. 失败函数的运用

第一:当然是运用于kmp算法的字符串比较

第二:用于求一个字符串的最大公共前后缀,即长度为next[n-1]+1,字符串为p0…p[next[n-1]]

第三: 用于求一个字符串中最大前缀,即max(next[])+1

3. 附言

如何求最大后缀?

两种算法,第一是倒转kmp计算过程的循环,第二是先倒转字符串后求出倒转字符串的最大前缀,再将该最大前缀倒转即是原字符串的最大后缀

如何求字符串的所有公共前后缀?第一大后的第二大,第三大?RT

由图我们可以理解到,第二大公共前后缀就是next[next[n-1]],第三大就是next[next[next[n-1]]],以此递归至-1为递归出口,就可输出所有公共前后缀