kmp模式串匹配

大二的时候百度看不懂，现在大三下学期了百度也看不懂。（实在是不能理解这个next数组究竟是怎么样工作的，为什么会得出那样的结果。）如果有好心人知道的话希望可以联系我告诉我（邮箱：4609019410@qq.com）

作用：字符串匹配

我们设匹配串为t，待匹配串为s，这个算法的功能就是在指定s中，从s的第i位字符开始搜索，判断在s中是否有t存在。

如果有则返回出现了t的首位字符位置（当然，这个数组是从0开始），如果没有则返回0。

通过next数组对匹配串t进行一个预处理，我们获得一个next数组。

下面的描述：string t：从0开始，next[]：从1开始

i=1;

这个next数组的意义是：对于我们要处理的字符串t里的第(i-1)字符对应的每一个next[i]元素

next[i]保存的是：从t[0]开始到t[i-1]的这一段字符串所有前缀与后缀的最大匹配长度。

next在kmp算法里发挥的作用：在每一次的匹配中，当碰上失配的情况（我们设初始态：t[0]与s[pos]开始比较，如果相等则两个指针同步增加变量。假设加到j时失配，即s[pos+j]!=t[j]）

我们可以利用next数组存储的信息，让它加速前进（而不是像朴素的模式匹配算法那样一位一位地挪，又从t[0]开始与s[pos]，提高匹配效率。）

几番周折还是弄不懂究竟是怎么运作的，所有只好先把实现的放上来，以后在琢磨是怎么回事了。以后弄明白了再回来说。。

#include<iostream>

#include<cstring>

using namespace std;

void get_next(string t,int *next)

{

	int i=1,j=0;

	next[1]=0;

	while(i<t.length())

	{

		if(j==0||t[i]==t[j])

		{

			i++;j++;

			next[i]=j;

		}

		else j=next[j];

	}

}

int index_KMP(string s,string t,int pos)

{

	int i=pos-1;

	int j=0;

	int next[255];

	get_next(t,next);

	//for(int i=1;i<=t.length();i++){

        //cout<<next[i]<<" ";

	//}

	//cout<<endl;

	while(i<s.length()&&j<t.length())

	{

		if(j==0||s[i]==t[j])

		{i++;j++;}

		else j=next[j];

	}

	if(j>=t.length())

	return i-t.length();

	else return 0;

}

int main()

{

	string a,b;

	cin>>a>>b;

	int w;

	cin>>w;

	int ans=index_KMP(a,b,w);

	cout<<ans<<endl;

	return 0;

}

巴特西

kmp模式串匹配

最新文章

热门文章