【给数学不好的人的KMP】字符匹配教程（二）简化运算是为了什么如何移位

【给数学不好的人的KMP】字符匹配教程（二）简化运算是为了什么如何移位

2013-01-21 14:12 676人阅读 评论(0) 收藏 举报

本文章已收录于：

分类：

技术学习不含代码（13）

作者同类文章 X

版权声明：本文为博主原创文章，未经博主允许不得转载。

昨天我们花了那么长的时间，基本搞明白了next数组的作用。我们费尽全力，只为了把上文中的else条件进行更改，即：不更新i,只移动j，从而达到节省时间，把效率从O(mn)降到O(M+N)的水平。

为什么可以略过去的最大位移等于next对应的值呢？

举个例子:

s=abacaba

p=abab，有s[3]!=p[3],如果是BF的话：i=3-3+1=1,j=0;

但是我们可以发现一个规律，因p[0]≠p[1],s[1]=p[1],必有s[1]≠p[0],又因p0=p2,s2=p2,所以必有s2=p0。因此,第二次匹配可直接从i=3, j=1开始。 这就是next数组移位的原理。

下面给出一个能用的模板:

[cpp] view plain copy print ?

1. int KMP_Find(string s,string t,int pos) //pos从0开始,输出绝对位置要加1   
2. {  
3.     build_next(t);  
4.     int i=pos;  
5.     int j=0;  
6.       
7.     for(i=pos;i<s.size();i++)  
8.     {  
9.         while(j>0 && s[i]!=t[j])  
10.         {  
11.             j=next[j-1];  
12.         }  
13.         if(s[i]==t[j])  
14.         {  
15.             j++;  
16.         }  
17.         else  
18.         {  
19.             j=0;  
20.         }  
21.         if(j>=t.size())   //目标串匹配结束   
22.         {  
23.             return i-t.size()+1;  
24.         }  
25.     }  
26.         return -1;  
27.       
28. }  

int KMP_Find(string s,string t,int pos) //pos从0开始,输出绝对位置要加1 
{
	build_next(t);
	int i=pos;
	int j=0;

	for(i=pos;i<s.size();i++)
	{
		while(j>0 && s[i]!=t[j])
		{
			j=next[j-1];
		}
		if(s[i]==t[j])
		{
			j++;
		}
		else
		{
			j=0;
		}
		if(j>=t.size())   //目标串匹配结束 
		{
			return i-t.size()+1;
		}
	}
		return -1;

}

kmp本身还有一些其他的形式，同样的，他的一个余数的性质可以用来求重复数等。与此衍生的还有bm算法等（不是剑圣。。）虽然只是搜索方向发生了改变，但本质却已经产生了极大的不同。下次再分解之。

• 上一篇【String+Map版】从poj 1002——487-3279的STL做法和若干陷阱来分析MAP
• 下一篇【map热手题】HDU 1004—Let the Balloon Rise

我的同类文章

技术学习不含代码（13）

http://blog.csdn.net

• •【考据】“烫烫烫”与“锟斤拷”的原理2014-07-07阅读32318
• •经典过桥问题的思路解析2013-07-28阅读445
• •网络流的入门思想2013-04-29阅读691
• •C语言中素数的快速判断和筛法创建。2013-01-30阅读2103
• •【一个OIER/ACMER算法练习的好去处】HDU ACM Steps王者之路系统简介~2013-01-28阅读2705

• •小学生玩ACM----栈和队列2013-08-04阅读1834
• •次小生成树的一点研究2013-05-04阅读326
• •【矩阵乘法入门】给数学不好的人的矩阵乘法模板教程2013-02-22阅读2628
• •【一个按标志分拆字符串的好方法】strtok函数简介及应用。2013-01-29阅读772
• •【给数学不好的人的KMP】字符匹配教程（一）next数组的理解2013-01-20阅读3274

更多文章