文档章节

kmp算法

laomd
 laomd
发布于 2017/02/23 11:23
字数 3012
阅读 3
收藏 0

本文参考小甲鱼数据结构与算法视频以及CSDN各dalao的博客,感谢小甲鱼老师在我学习数据结构与算法过程中给的启示!!!

 

【传统字符串匹配算法的缺憾】

暴力法c++代码:

#include <iostream>
#include <string>
using namespace std;

//if found,return the position of s in main_string,else return 0;
int BF(const string& main_string,const string& s);

int main(int argc, char const *argv[])
{
	string main_string,s;
	cin >> main_string >> s;
	int pos = BF(main_string,s);
	if(pos)
		cout << "Found in position " << pos << endl;
	else
		cout << "Not found" << endl;
	return 0;
}

int BF(const string& main_string,const string& s)
{
	int L = main_string.size(),l = s.size();

	for (int i = 0; i <= L - l; ++i)
	{
		if(s == main_string.substr(i,i + l))
			return i + 1;
	}
	return 0;
}		

【代码思想】

        传统匹配思想是,从目标串main_string的第一个字符开始扫描,逐一与模式串的对应子串进行匹配,若相等,则返回模式串在目标串中第一次出现的位置,否则退回到main_string的第二个字符,重复上述步骤,直到整个s在main_string中找到匹配,或者已经扫描完整个目标串也没能够完成匹配为止。

        这样的算法理解起来很简单,实现起来也容易,但是其中包含了过多不必要的操作,也就是在目标串中,有些字符是可以直接跳过,不必检测的

 

【kmp算法导引】

怎么理解不必要的操作?先看有关kmp算法四个思路启发。

1.启发一   

        目标串main_string:abcdefg       模式串s:abcdE

        我们发现,模式串与目标串在e与E失配了,很可惜只差一个字符,不然就天下太平了!那下一步要怎么做?没错,只需要把模式串右移到失配位置继续比较,也就是s的a移到main_string的e处。为什么呢?

        通过观察,我们知道模式串失配字符E前面的字符abcd里面,每一个字符都不相等,也就是s[0]!=s[1]!=s[2]!=s[3]!=s[4],根据失配前的信息,我们知道s与main_string的0 1 2 3位置是匹配的,所以是s[0]不可能等于main_string的0 1 2 3,但是是s[0]!=s[4]且main_string[4]!=s[4],我们就没法知道s[0]和main_string[4]是否相等,因而下一步就是比较s[0]与main_string[4]了,也就是把模式串右移到失配位置。

    这种情况下,不必要的比较就是是s[0]与main_string的1 2 3开始的比较

2.启发二

        引入概念:

                前缀:比如abcd的前缀是a,ab,abc

                后缀:比如abcd的后缀是d,cd,bcd

        目标串main_string:bebbcdef        模式串s:bebcd

        模式串与目标串在第4个位置失配,如果按照思路启发一,下一步目标串就是从main_string[3]开始,也就是比较bcde与bbcd,这样我们就与正确答案擦肩而过了!

        实际上,通过观察,模式串失配字符c前面的字符beb里面,有相等的前缀b(s[0])和后缀b(s[2]),而根据失配前的信息,两串在012号元素是匹配的,也就是main_string[0]==s[0],main_string[1]==s[1],main_string[2]==s[2],而s[0]==s[2],所以main_string[2]==s[0],所以s[0]不应该直接跳到失配的main_string[3]的位置,而应该是后缀b匹配的main_string[2]的位置

3.启发三

        目标串main_string:bbcdbbcdbbcf        模式串:bbcdbbcf

        这是启发二的加强版,相等前缀后缀bbc的长度大于1,其实原理还是一样,失配后把s右移到后缀的位置。 

4.启发四

        目标串main_string:ssssscde       模式串:ssssa

        这又是启发三的加强版,相等前缀(0-2)后缀(1-3)ssss有重叠的部分但这不影响方法,失配后把s右移到后缀的位置。

        总而言之,如果失配前的字符没有相等的前后缀,就简单粗暴地把s右移到失配位置,否则把s右移到后缀位置。

 

【next数组】    

       在KMP算法中有个数组,叫做前缀数组,也有的叫next数组,每一个子串有一个固定的next数组,它记录着字符串匹配过程中失配情况下可以向前多跳几个字符,当然它描述的也是子串的对称程度,程度越高,值越大,当然之前可能出现再匹配的机会就更大。

       这个next数组的求法是KMP算法的关键,但不是很好理解。

        1、用一个例子来解释,下面是一个子串的next数组的值,可以看到这个子串的对称程度很高,所以next值都比较大。

位置i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

前缀next[i]

0

0

0

0

1

2

3

1

2

3

4

5

6

7

4

0

子串

a

g

c

t

a

g

c

a

g

c

t

a

g

c

t

g

申明一下:下面说的对称不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。

(1)逐个查找对称串。

这个很简单,我们只要循环遍历这个子串,分别看前1个字符,前2个字符,3个... i个 最后到15个。

第1个a无对称,所以对称程度0

前两个ag无对称,所以也是0

依次类推前面0-4都一样是0

前5个agcta,可以看到这个串有一个a相等,所以对称程度为1前6个agctag,看得到ag和ag对成,对称程度为2

这里要注意了,想是这样想,编程怎么实现呢?

只要按照下面的规则:

a、当前字符的前一个字符的对称程度为0的时候,只要将当前字符与子串第一个字符进行比较。这个很好理解啊,前面都是0,说明都不对称了,如果多加了一个字符,要对称的话最多是当前的和第一个对称。比如agcta这个里面t的是0,那么后面的a的对称程度只需要看它是不是等于第一个字符a了。

 

b、按照这个推理,我们就可以总结一个规律,不仅前面是0呀,如果前面一个字符的next值是1,那么我们就把当前字符与子串第二个字符进行比较,因为前面的是1,说明前面的字符已经和第一个相等了,如果这个又与第二个相等了,说明对称程度就是2了。有两个字符对称了。比如上面agctag,倒数第二个a的next是1,说明它和第一个a对称了,接着我们就把最后一个g与第二个g比较,又相等,自然对称成都就累加了,就是2了。

 

c、按照上面的推理,如果一直相等,就一直累加,可以一直推啊,推到这里应该一点难度都没有吧,如果你觉得有难度说明我写的太失败了。

(2)回头来找对称性

当然不可能会那么顺利让我们一直对称下去,如果遇到下一个不相等了,那么说明不能继承前面的对称性了,这种情况只能说明没有那么多对称了,但是不能说明一点对称性都没有,所以遇到这种情况就要重新来考虑,这个也是难点所在。

在这里依然用上面表中一段来举个例子:   

位置i=0到14如下,我加的括号只是用来说明问题:

(a g c t a g c )( a g c t a g c) t

我们可以看到这段,最后这个t之前的对称程度分别是:1,2,3,4,5,6,7,倒数第二个c往前看有7个字符对称,所以对称为7。但是到最后这个t就没有继承前面的对称程度next值,所以这个t的对称性就要重新来求。

这里首要要申明几个事实

1、t 如果要存在对称性,那么对称程度肯定比前面这个c 的对称程度小,所以要找个更小的对称,这个不用解释了吧,如果大那么t就继承前面的对称性了。

2、要找更小的对称,必然在对称内部还存在子对称,而且这个t必须紧接着在子对称之后。

如下图说明。

 

从上面的理论我们就能得到下面的前缀next数组的求解算法。

void get_next(const string& s, int next[])

{
     int len = s.size();//模式串长度。
     next[0] = 0;//0号元素前面什么都没有,当然也就没有所谓的前后缀

     for(int i = 1; i < len; i++)
     {
         int k = next[i - 1];
         //不断递归判断是否存在子对称,k=0说明不再有子对称,Pattern[i] != Pattern[k]说明虽然对称,但是对称后面的值和当前的字符值不相等,所以继续递推
         while( s[i] != s[k]  &&  k != 0 )               
             k = next[k - 1];     //继续递归
         if( s[i] == s[k])//找到了这个子对称,或者是直接继承了前面的对称性,这两种都在前面的基础上++
              next[i] = k + 1;
         else
              next[i] = 0;       //如果遍历了所有子对称都无效,说明这个新字符不具有对称性,清0
     }
}

当然还有另外一种求解next数组的算法(笔者也不懂,望dalao指教):

void get_next(const string& s,int* next)
{
	int l = s.size();

	next[0] = 1;

	int j = 1,k = 0;//j is the index of next, and k is the offset of each element in next

	while(j < l)
	{
		if(k == 0 || s[j] == s[k])
		{
			j++;
			k++;
			next[j] = k;
		}		
		else
			k = next[k];
	}
}

【kmp算法终极实现】

第一个版本:

#include <iostream>
#include <string>
using namespace std;

//if found,return the position of s in main_string,else return 0;
int kmp(const string&,const string&);
int main(int argc, char const *argv[])
{
	string main_string,s;
	cin >> main_string >> s;
	int pos = kmp(main_string,s);
	if(pos)
		cout << "Found in position " << pos << endl;
	else
		cout << "Not found" << endl;
	return 0;
}
​
void get_next(const string& s, int next[])

{
     int len = s.size();//模式串长度。
     next[0] = 0;//0号元素前面什么都没有,当然也就没有所谓的前后缀

     for(int i = 1; i < len; i++)
     {
         int k = next[i - 1];
         //不断递归判断是否存在子对称,k=0说明不再有子对称,Pattern[i] != Pattern[k]说明虽然对称,但是对称后面的值和当前的字符值不相等,所以继续递推
         while( s[i] != s[k]  &&  k != 0 )               
             k = prefix[k - 1];     //继续递归
         if( s[i] == s[k])//找到了这个子对称,或者是直接继承了前面的对称性,这两种都在前面的基础上++
              next[i] = k + 1;
         else
              next[i] = 0;       //如果遍历了所有子对称都无效,说明这个新字符不具有对称性,清0
     }
}

​
int kmp(const string& S,const string& T){
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空,
  int next[T.size()];
  	get_next1(T,next);

  	int index,count = 0;
  	for(index = 0; index < S.size(); ++index){
    	int pos = 0;
     	int iter = index;
     	while(pos < T.size() && iter < S.size()){
        	if(S[iter] == T[pos]){++iter;++pos;}
        	else{
            	if(pos == 0) ++iter;
            	else pos = next[pos - 1] + 1;
        	}
     	}
      	if(pos == T.size() && (iter - index) == T.size()) ++count;
  	}
  	return count;
}

第二个版本:

#include <iostream>
#include <string>
using namespace std;

//if found,return the position of s in main_string,else return 0;
int kmp(const string&,const string&);
int main(int argc, char const *argv[])
{
	string main_string,s;
	cin >> main_string >> s;
	int pos = kmp(main_string,s);
	if(pos)
		cout << "Found in position " << pos << endl;
	else
		cout << "Not found" << endl;
	return 0;
}

void get_next(const string& s,int* next)
{
	int l = s.size();

	next[0] = 1;

	int j = 1,k = 0;//j is the index of next, and k is the offset of each element in next

	while(j < l)
	{
		if(k == 0 || s[j] == s[k])
		{
			j++;
			k++;
			next[j] = k;
		}		
		else
			k = next[k];
	}
}

int kmp(const string& main_string,const string& s)
{
	int L = main_string.size(),l = s.size();
	int i = 0, j = 0;

	int next[l] = {0};
	get_next(s,next);
	
	while(i < L && j < l) {
	    if(j == 0 || main_string[i] == s[j])
	    {
	    	i++;
	    	j++;
	    }
	    else
	    	j = next[j];
	}

	if(j >= l)
		return i - l + 1;
	else
		return 0;
}

当然这个kmp算法代码不是最优的,这里不做讨论!

终于大功告成了!!!!

© 著作权归作者所有

共有 人打赏支持
laomd
粉丝 0
博文 31
码字总数 12000
作品 0
广州

暂无文章

qduoj~前端~二次开发~打包docker镜像并上传到阿里云容器镜像仓库

上一篇文章https://my.oschina.net/finchxu/blog/1930017记录了怎么在本地修改前端,现在我要把我的修改添加到部署到本地的前端的docker容器中,然后打包这个容器成为一个本地镜像,然后把这...

虚拟世界的懒猫
46分钟前
1
0
UML中 的各种符号含义

Class Notation A class notation consists of three parts: Class Name The name of the class appears in the first partition. Class Attributes Attributes are shown in the second par......

hutaishi
58分钟前
0
0
20180818 上课截图

小丑鱼00
今天
1
0
Springsecurity之SecurityContextHolderStrategy

注:下面分析的版本是spring-security-4.2.x,源码的github地址是: https://github.com/spring-projects/spring-security/tree/4.2.x 先上一张图: 图1 SecurityContextHolderStrategy的三个......

汉斯-冯-拉特
今天
0
0
LNMP架构(Nginx负载均衡、ssl原理、生成ssl密钥对、Nginx配置ssl)

Nginx负载均衡 网站的访问量越来越大,服务器的服务模式也得进行相应的升级,比如分离出数据库服务器、分离出图片作为单独服务,这些是简单的数据的负载均衡,将压力分散到不同的机器上。有时...

蛋黄_Yolks
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部