字符串匹配——KMP算法

  1. 云栖社区>
  2. 博客>
  3. 正文

字符串匹配——KMP算法

兰亭侠 2014-09-02 21:26:00 浏览371
展开阅读全文

关于KMP算法的分析,我觉得这两篇博客写的不错:

http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

http://blog.csdn.net/v_JULY_v/article/details/6545192

下面的笔记也是参考了这两篇博客的。


KMP算法是最有名的字符串匹配算法了。它是BF算法的改进版,至于是如何改进的,先引用上述第二篇博客里的一段话:


        “在继续分析之前,咱们来思考这样一个问题:为什么快排或者堆排序比直接的选择排序快?直接的选择排序,每次都是重复地比较数值的大小,每扫描一次,只得出一个最大(小值),再没有其它的成果。而快排,每扫一次,将数据分成了两部分,右边的数据都大于左边的数据,所以在下一次比较的时候,这两部分元素之间就不用比较了。再看堆排序,建堆的过程也是O(n)的比较,但比较的结果得到了最大(小)堆这种三角关系,之后的比较就不用再每一个都需要比较了。

        由上述思考,咱们总结出了一点优化的归律:采用一种简单的数据结构或者方式,将每次重复性的工作得到的信息记录得尽量多,方便下一次做同样的工作,这样将带来一定的优化。”


总结上面这段话的核心思想,就是把循环中要重复做的工作提取到循环外完成,从而提高效率。


下面用一个例子演示KMP匹配的过程。其中涉及的三个数据如下:

        source:源串,即要匹配的母船

        pattern:模式串,即子串

        next数组:其每个元素对应pattern的每个字符,表示当该字符pattern[j]不匹配source[i]时,应该从pattern的哪个下标开始重新匹配当前的source[i],具体求法后面介绍


本例中source为ABCABCABDE,pattern为ABCABD,第一次匹配,前5个字符均匹配成功,匹配第6个字符时如下:



此时发现source[5]和pattern[5]不匹配,BF算法的做法是从source[1]开始从新匹配pattern,即像下面这样:



而KMP算法则不会再去重新比较source[1...4]了,它会利用next的信息调整pattern。因为next[5]=2,所以下一次匹配将当前的source[5]和pattern[2]比较,即像下面这样:



这时发现source[5]和pattern[2]匹配,继续往下比较,直至pattern中所以元素都比较完了,如下:



此时已经在母串中找到了子串,i=9,m=6,所以返回的下标为i-m=3。


这样整个匹配过程就完了,感觉不过瘾吗,前面两篇推荐的博客里有更长的匹配串分析。


把上面的过程翻译成代码,也就是KMP算法的实现,如下:

int KMP(char *source, char *pattern)
{
	int i, j, m, n;
	int *next;

	i = 0;
	j = 0;
	m = strlen(pattern);
	n = strlen(source);
	next = (int *)malloc(m * sizeof(int));

	Next(pattern, next);<span style="white-space:pre">	</span>// 这是求next数组的函数,后面解释

	while (i < n && j < m)
	{
		if (j == -1 || source[i] == pattern[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}

	free(next);

	if (j == m)
	{
		return i - m;
	}
	else
	{
		return -1;
	}
}

下面来看next数组是如何求得的。


如前所述,next数组里保存的就是pattern[j]与母串中的字符不匹配时,该用哪个下标继续和这个字符匹配。若next[j]=k,则有:pattern[0...k-1] = pattern[j-k...j-1],而且这个k是最大的,即不会有pattern[0...k] =pattern[j-k-1...j-1]。


反过来想,如果已经知道了pattern[0...k-1] = pattern[j-k...j-1],next[j]是多少呢?要分两种情况考虑:

        1. pattern[k] != pattern[j],则next[j] = k

        2. pattern[k] = pattern[j],则next[j] = next[k]

第二种情况是因为,若pattern[k] = pattern[j]时,也使next[j]=k;则在pattern[j]于母串不匹配的情况下,再拿pattern[next[j]]即pattern[k]去比较的话,肯定也是不匹配的。这是隐藏的重复工作。使next[j] = next[k]就能避免这种重复工作。


那么怎么又能保证pattern[j]不会等于pattern[next[k]]呢?不急,一步一步想:最开始有next[0]=-1,如果pattern[1]=pattern[0],那么由规则2,next[1]=next[0]=-1;再如果pattern[2]=pattern[1],那么next[2]=next[1]=-1。看到了吗,三个一样的字符,如果是next依次为前一个元素的情况,最终都会是最前面那个next值,这就保证了最大的减少重复工作。


好吧,上面的解释很挫,意会吧。其实就跟离散树一样,同一个集合的元素都有相同的根。


有了上面的规则后,求next数组就比较方便了。用动态规划的策略很好实现:

void Next(char *pattern, int *next)
{
	int i, j, n;

	i = 0;
	j = -1;
	next[0] = -1;
	n = strlen(pattern);

	while (i < n - 1)
	{
		if (j == -1 || pattern[i] == pattern[j])
		{
			++i;
			++j;

			if (pattern[i] != pattern[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}
		}
		else
		{
			j = next[j];
		}
	}
}

是不是感觉和KMP的框架很像,其实就是一回事,都是子串匹配,都利用了next数组。

不同之处在于:KMP是source匹配pattern,Next是一直从pattern的头部开始匹配后面所有的序列;在Next里面,next数组还没有完全生成,是利用前面生成的next加上匹配结果生成下一个next,这就是动规的策略。


网友评论

登录后评论
0/500
评论
兰亭侠
+ 关注