前言:
引入 KPM 算法的前提是 , B-F算法中,匹配失败后不必完全从头再来 , 找到可以利用的信息 , 可以进行跳跃性匹配
下面 , 我们对字符串匹配的一些思路进行剖析:
开始匹配的操作 ,我们会让 目标串 s , 和 模式串进行对齐,就像如图所示:
我们当然是从串 t 的头结点开始对比
对比 第一个元素 , 符合
然后对比第二个 元素符合
对比第三个元素 , 不相等
此时 , 按照我们 B-F算法 , 不相等 , 我们就需要重新从 串 s 的第二个元素, 进行和 串 t 进行比较了
如图 :
但是 , 此时我们注意到 , 我们开头已经对比了 串 t 和 串 s 两个元素重合 , 并且他们互不相等 , 说明再次把串 t 的开头 和 串 s 的第二个元素是不明智的选择
因为 , 我们既然要寻找和串 t 相等的串 , 首先要保证的就是 , 串 t 的头结点要和串 s 元素先匹配上, 然后我们才能继续后续的对比
我们现在前两个节点已经重合, 并且他们互不相同 , 就没必要再移动一位了重合比较了
所以 , 我们直接 将串 t 开头和 串 s 的第三个元素进行比较即可
我们接着对比 , a 相等 , b 相等 , c 相等 , a 相等 , 当比较到串 t 的第五个元素时 , b 和 c 不相等 ,
此时, 我们如果还采取 B-F算法当然也是可以的 , 逐个将 串t 和 对比初始位置后移的串 s 进行对比 ,
我想 , 上面的步骤有些是没必要的 , 因为我们此时分析 :
串 t 此时我们已经对比了五个元素 , 前 四个已经对比符合了 ,
我们现在第五个元素, 对比到了不同元素 , 我们能直接把对比过的字符串抛弃吗?
意思就是说 , 我们能下定论, 已经对比过的字符, 不会再有可以匹配的子串了呢?
能直接如下图所示吗?
聪明的我们, 会发现 , 我们就算对比重合过的字符 , 遇到不同的字符 , 我们也不能直接把 比较重合过的字符全部抛弃 , 除非对比过的字符互不相同 , 那 我们直接略过也没事 ,
但是如果, 我们对比过的字符 , 有和 串 t 头结点相等的节点 , 我们就不能略过了
上图, 标蓝 部分 , 我们在我们在对比的时候已经对比过了 , 我们会发现 串 t 里面有两个头节点 , 那当我对比到 第二个头结点之后的一个节点的时候 , 我们如果发现不同字符 , 我们就可以把第二个头结点当作头结点, 然后后续接着让 串 t 的第二个节点和 串 s 进行比较
我们上面的意思就是 , 假如现在有一个
当串 s 和 串 t 元素进行比较时 , 当一个字符不匹配的时候 , 我们必然要让 串 t 开头 往后移动
但是逐个比较的话 , 有些节点是没必要比较的 , 如下图:
明明知道, 前五个字符两个串对比符合了, 并且五个字符互不相同 , 就没必要逐个错峰比较了,
直接跳过这五个元素 , 让 串 t 第一个元素和串 s 第五个元素进行比较
但是 , 有的情况 , 当比较到不同字符时 , 那个字符前面有和头结点相同的子串的话 ,我们就可以直接把 头结点子串的位置, 拉到 不同字符前面的头节点子串的位置 , 这样就不会错过重合的机会了.
如下图
经过上面的分析 , 我们得出, 如果要准确把握模式串 t 每个字符 比较到不同的字符的时候 ,应该跳到串 t 哪个字符再和 串 s那个元素进行比较 , 就需要找出每个字符前面的和头结点子串相等的子串 ,
那当子串有很多呢 ? 找哪一个呢?
我们就需要引入前缀串和后缀串
作者能力有限 , 下一篇博客 ,转载大佬解析 ,我这里只做思路引导 .
c代码:
#include <stdio.h>
#include "sqString.h"
void GetNext(SqString t , int next[])
{int j,k;j = 0;k = -1;next[0] = -1;while(j<t.length-1){if(k == -1 || t.data[j] ==t.data[k]){j++;k++;next[j] = k;}else{k = next[k] ;}}
}
//进行验证
int KMPIndex(SqString s, SqString t)
{int next[MaxSize],i=0,j=0;GetNext(t,next);while(i<s.length && j<t.length){if(j == -1 || s.data[i] == t.data[j]){i++;j++;}else{j = next[j];}}if(j >= t.length){return(i - t.length);}else{return(-1);}
}
int main()
{SqString s,t;StrAssign(s,"ababcabcacbab");StrAssign(t,"abcac");printf("s:");DispStr(s);printf("t:");DispStr(t);printf("位置: %d\n",KPMIndex(s.t));return 0;
}
