KMP算法
引言
比如字符串为abababaababacb,要查找ababacb是否在其中,或者在其中的哪个位置,比如匹配主串的数组指针为i,匹配模式串的指针为j
暴力算法:每次匹配失败后,俩个指针都回溯,从头开始匹配
KMP算法的核心:
利用匹配失败后的信息,劲量减少模式串与主串的匹配次数,一道道快速匹配的目的
比如字符串ababacb
前缀集合为 {a,ab,abab,ababa,ababac}
后缀集合为{b,cb,acb,bacb,abacb,babacb}
比如匹配失败时,不只是代表了匹配失败,而是代表前面的字符都匹配成功了
那么j指针到底要回溯到哪个位置呢?
我们要在已获得的信息中做到不遗漏的同时尽可能多的匹配
匹配方式
我们需要找到:A子串的后缀集合与B子串的前缀集合的交集里最长的那个元素
使b串后移的最少,且在已知信息中匹配的最多
这个最长元素的长度:就是j指针回溯的位置
匹配失败代表着前面J个子串是匹配成功的
所以这句话也可以改为B子串的前缀集合与它本身的后缀集合的交集
通过隐藏信息:匹配失败时A串与B串存在着一段相同的子串
所以综上可得,J指针回溯的位置只与B串有关,与A串无关
所以其实在A和B字符串匹配之前,就通过B串计算出回溯的位置,然后存在一个next数组里
next与B串形成映射数组存的数据next[i]计算B[1]~B[i]的最长公共前后缀的长度
总结
- i,j初始化为0,如果A[i+1]=B[i+1],i++,j++然后继续匹配
- 如果A[i]!=B[j+1]回溯J到next[j]知道a[i+1]==B[j+1],这里面有一种情况(B传需要移动到i的后面)J回溯到0时也不能满足使A[i+1]=B[j+1]
- 当j=m时,输出位置,继续匹配
匹配流程
比如匹配到这里失败了此时的嘴馋公共前后缀就是aba,然后就将b串后移(在代码上其实就是将j指针回溯)
因为aba已经匹配成功了,然后这里又匹配失败了
构建next数组
我们可以用B传自己与自己匹配,B[1]~B[i]的前缀与它的后缀匹配 后缀为主串 前缀为模式串,以递推的方式求出next数组
- 如果匹配 next[i]=j+1,j是b串前缀的指针也就是当前字符串匹配之前的最长公共前缀的长度这里匹配成功了要+1
- 如果不匹配:回溯j指针,j=next[j]直到匹配成功
然后从这里开始匹配,然后蓝线的这一段是相同的,不需要在匹配这一段,然后发现第一段就不相同了,这时候最长公共前后缀就是a字符串,然后把B串向后移动一位
这时候发现他们就一个,根本没有最长公共前后缀,没有j就是0了,所以b串又后移了一位
这时候就匹配上了
但如果这俩个字符不匹配的话,这时候就需要i往后推了,所以就不需要j=0的时候(指向最前面的空位置),就要忽略j,去把I向后退
解决了匹配的问题,下面就是怎么构建匹配数组了