首页 > 代码库 > KMP算法 学习笔记

KMP算法 学习笔记

kmp算法在很多人看来是如此的厉害,很早之前就学过了,但是各种看不懂把我拦住了,现在重新拾取,来写一下个人的学习总结。

kmp看毛片算法(小甲鱼教的)(在这给小甲鱼做个广告,我个人看来小甲鱼讲的数据结构很好,很有趣。个人创业不容易,希望大家多多支持www.fishc.com小甲鱼,我跟小甲鱼素不相识,只是有用的东西大家分享)


好了言归正传。

如果你之前看过kmp算法没有看懂希望在这不要带着一种恐惧感,如果你没看过那是更好。

网上有很多详细教程,但是大部分都很啰嗦,容易把人看晕。

kmp算法没有什么难的,你只要记住一点:kmp算法就是提前处理一下我们要找的字符串。

我们怎样来处理要找的字符串呢?

举个例子就是....例子好复杂。

我直接说视频吧。我想没有很么能比视频讲的明白了 。

视频的下载地址在这里

 http :

//pan.baidu.com/s/1eQtceWE

好了,继续说,视频上讲的简单明了。很适合我们的思维。

在这里补充一点就是,在视频中小甲鱼的

else
		{
			j=next[j];
		}

没有讲明白,我给大家补充一下我的想法。(当大家看了视频就会知道是哪里了)。

就是当s[i]!=s[j]的时候要将j返回到next[j]所指的位置,大家可以这样来想,我们的next的数组是干嘛的,不就是为了不匹配的时候我们向前来跳转的嘛,这里就直接用上就行了。可能我说的也有一点模糊,但是大家想一下,现在把前面这个字符串当做是要找的字符串,后面这个是那个s串(也就是长的串(这样说不太好,但是容易理解)),这样我们找不到,自然就要回到next【j】了。对吧。

好了下面贴上看完视频后自己还原的代码:

#include<iostream>
#include<string>
using namespace std;
//kmp算法
//next数组的构建
void get_next(string s,int * next)
{
	int i=0;
	int j=-1;
	next[0]=-1;
	while(i<s.size())
	{
		if(j==-1||s[i]==s[j])
		{
			i++;
			j++;
			next[i]=j;
		}
		else
		{
			j=next[j];
		}
	}
}
int main()
{
	string s,t;
	cin>>s>>t;
	int next[1000];
	get_next(t,next);
	//下面是kmp算法的实现 我是从开头开始查询的 返回了位置。
	int i=0,j=0;
	int ssize=s.size();
	int tsize=t.size();
	while(i<ssize&&j<tsize)
	{
		if(j==-1||s[i]==t[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j==t.size())
	{
		cout<<i-tsize+1<<endl;
	}
	else
	{
		cout<<"no"<<endl;
	}
	system("pause");
}
其中存在视频中所说的优化问题下面来进行优化:

#include<iostream>
#include<string>
using namespace std;
//kmp算法
//next数组的构建
void get_next(string s,int * next)
{
	int i=0;
	int j=-1;
	next[0]=-1;
	while(i<s.size())
	{
		if(j==-1||s[i]==s[j])
		{
			i++;
			j++;
			if(s[i]==s[j])
				next[i]=next[j];
			else
				next[i]=j;
		}
		else
		{
			j=next[j];
		}
	}
}
int main()
{
	string s,t;
	cin>>s>>t;
	int next[1000];
	get_next(t,next);
	//下面是kmp算法的实现 我是从开头开始查询的 返回了位置。
	int i=0,j=0;
	int ssize=s.size();
	int tsize=t.size();
	while(i<ssize&&j<tsize)
	{
		if(j==-1||s[i]==t[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j==t.size())
	{
		cout<<i-tsize+1<<endl;
	}
	else
	{
		cout<<"no"<<endl;
	}
	system("pause");
}

好了!

感谢自己坚持。