大二上学期的时候,学习数据结构,偶尔接触了KMP算法,那个时候没特别理解,为了应付考试,就仅仅是看了前缀后缀那个知识点,刚刚打算好好看一看,因为最近在学习java,老师提到了一句,自己刚刚查阅资料研究的时候,感觉对于小白来说很难理解,一下是我的一些看法。
KMP算法的用处
在一个长的字符串里寻找一个短的字符串,有一种暴力解法,举个例子。
** a b a b a**
a b a
在ababa中寻找aba,可以这样对照。(粗的是一样的)如下图;
这个暴力求解,我们可以看出,只要主串足够长,那么在主串中寻找子串的位置就越难!假设主串长度是m,而子串长度是n , 那么这个计算相当于是一个双重循环!(如上图ababb中寻找abb)
先从主串a开始依次对比子串的abb,如果不对就从主串的b开始再依次对比子串的abb。就有点类似于
for(ababb){
for(abb){
}
}
这样显然是很慢的,那么有没有一种方法,因为子串是固定呢,能不能在往下移的时候多移一点呢?或者说省略一点点呢?比如直接在不同的地方跳过?
虽然上面我举的例子是错误的方法,但是这样我们就有了一个想法,当比较不同的时候,我们可以通过一些方式跳过一些步骤,从而省略时间!
既然我们知道了可以跳过一些步骤,具体要跳过多少步骤呢?从比较不同的地方开始跳跃吗?显然是错误的!这就是KMP算法的精髓!我们继续看例子(这次的例子可是正确的咯,也会反驳我之前那个错误的方法)
abaabaabac
abaabac
比如这个例子
很明显第七个位置是不同的,那么直接跳过6个步骤对吗?显然不对,因为只要跳过三个步骤就可以了
aba abaabac
abaabac
我们怎么看出的呢?
abaabaabac
abaabac
有没有发现这三个是相同的
我们就跳过三个步骤(6-3)
因为前6个都相同,所以6来源于这里,因为abaaba前面和后面有aba是相同的,所以是3
那么具体跳过几个步骤,如何来计算呢?这就是kmp算法中的next[ ]
NEXT[ i ] = j
这个数组有什么意思呢?
我们先来理解前缀和后缀
比如用ababa来举例
前缀就是从前开始 a,ab,aba,abab
后缀就是从后开始 a,ba,aba,baba
我们可以看出前缀和后缀相等的最大位数是aba,是三位
我们就可以这样表示 next[5]=3,
其中5是表示这个字符串一共有多少位数,3表示这个字符串前缀和后缀相等的最大位数
跳过的步骤就是 5 - 3 = 2
这就是 next[ ] 数组的用法
我们看之前例子
abaabaabac
abaabac 第七个出现不同,说明之前的6个都是符合的 (next[6])
我们把之前的6个拿出来
abaaba
前缀a,ab,aba,abaa,abaab
后缀a,ba,aba,aaba,baaba
那么这个相等的就是aba
next[6]=3
所以我们跳过6-3个
aba abaabac
abaabac 就变成了这样
这样不会既不会因为减少步骤而落下一些相同的,也会减少时间
这就是KMP算法的精髓
如何用编程语言实现next[i]就需要自己更加的了解才可以!
理解了这个,KMP你就理解了大概了,就是在筛选过程中,跳过一些没有必要的过程来减少计算时间,这是我自己的理解!如果以后我有更好的讲解方法,我会再次更新帮助初学者们。