[POJ3461]Oulipo 字符串匹配 详解KMP算法

给出一个文本和一个膜式串,求膜式串在文本串中出现了多少次.
这是一道裸字符串匹配问题,可以使用hash或KMP解决.今天介绍经典的KMP算法.
先来看看一个字符串匹配的实例:
BBCXABCDABXABCDABCDABDE
ABCDABD
我们都会暴力匹配算法:弄一个文本串指针i和一个膜式串指针j,然后比较两个位置的字符是否相同.如果相同,就i++,j++,否则i和j要回溯.
这样的算法之所以效率低下,就是因为失配时要回溯,这个过程太耗费时间.它没有充分利用膜式串的性质,因而不够理想.
那么,怎么才能提高算法效率呢?显然,我们要想办法让文本串指针i不回溯,做到O(len)匹配.

看:
BBCXABCDABXABCDABCDABDE
ABCDABD

当膜式串匹配到红色部分时,两个字符串失配了.此时,我们可以保持i不动,将j回溯到j前面最长的前缀后缀的下一个位置.这相当于省略了暴力匹配中的一段过程.

所谓前缀后缀,顾名思义,就是既是前缀又是后缀的子串.以本字符串为例,现在j=6(从0开始),那么j前面最长的前缀后缀就是"AB"这个串,对吧?好的,那么既然后缀里面的AB都能匹配上,前缀里的AB自然也能匹配上;又因为它是最长的,所以不必担心省略掉的暴力匹配过程中包含着一次成功的匹配.思考一下这两个条件.

那么,我们提前处理出膜式串中每个位置前的最长前缀后缀长度,将它们存储到一个next[]数组中,不就可以完成O(len)无回溯匹配了嘛!至于求next[]数组的递推过程,就在下面的代码中.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int t,ans;
int slen,plen;
char s[1002333],p[10233];
int next[10233];
void getnext()
{
	plen=strlen(p);
	int j=0,k=-1;
	next[0]=-1;
	while(j<plen)
	{
		if(k==-1||p[j]==p[k])
		{
			next[j+1]=k+1;
			j++,k++;
		}
		else k=next[k];
	}
}
void kmp()
{
	int i=0,j=0;
	slen=strlen(s);
	while(i<slen)
	{
		if(j==-1||s[i]==p[j])i++,j++;
		else j=next[j];
		if(j==plen)j=next[j],ans++;
	}
}
int main()
{
	cin>>t;
	while(t--)
	{
		ans=0;
		scanf("%s",p);
		scanf("%s",s);
		getnext();
		kmp();
		printf("%d\n",ans);
	}
	return 0;
}

 

《[POJ3461]Oulipo 字符串匹配 详解KMP算法》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注