串的匹配 (KPM算法)

前言:

引入 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 
#include "sqString.h"
void GetNext(SqString t , int next[])
{
	int j,k;
	j = 0;
	k = -1;
	next[0] = -1;
	while(j-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
	{
		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;
}