`
edr_
  • 浏览: 169810 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

算法系列之KMP算法

阅读更多
串的模式匹配算法
模式匹配是指将两个模式作为输入,计算模式元素之间语义上的对应关系的过程,在数据结构中模式匹配是字符串的基本运算之一。
有两个字符串S和T,字符串S称为正文(被匹配字符串),字符串T称为模式(匹配字符串),要求找出模式T在正文S中的首次出现的位置。一旦模式T在正文S中找到,就说发生一次匹配。
示例  目标 S : “Beijing”
         模式 T : “jin”
         匹配结果 = 3

首先来说说一般情况下的匹配模式:在字符串T跟字符串P上分别定义两个指针i,j,从0开始,如果S[i]==T[j],i++;j++;指针下移,继续循环,一直到字符串T或者字符串P结束,如果匹配成功,返回i-j;如果中间出现S[i]!=T[j],则i回溯(i=i-j+1),而j也回溯(j=0),继续循环。还是图比较好理解,见下图,从左到右(i=5-5+1=1,下图属于笔误,谢谢网友提醒)

代码如下(java实现):
//------------串的模式匹配原声算法----------------
	public void index(char[] test,char[] pattern) {
		int test_len=test.length;
		int pattern_len=pattern.length;
		int i=0,j=0;
		while (i<test_len) {
			if (j==pattern_len) {
				System.out.println("配对成功:起始下标(从0开始)为---"+(i-j));
				break;
			}
			if (test[i]==pattern[j]) {
				i++;j++;
			}else {
				if (j==0) {
					i++;j++;
				}else {
					i=i-j+1;
					j=0;
				}
			}
		}
	}
	public static void main(String[] args) {
		char[] test="abcabcabdaaaaa".toCharArray();
		char[] pattern="abcabd".toCharArray();
		KMP kmp=new KMP();
		kmp.index(test, pattern);
	}


改进算法---KMP算法
百度百科:kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。
效果图如下:

至于j要回溯多少则关系到next函数值的求解:getNext()
       1.前两位必定为-1和0;
       2.计算第三位(下标为2)的时候,看第二位b的next值,为0,则把b和0下标对应的a进行比较,不同,则第三位a的next的值为0;
       3.计算第四位(下标为3)的时候,看第三位c的next值,为0,则把c和0下标对应的a进行比较,不同,则第三位a的next的值为0;
       4.计算第五位(下标为4)的时候,看第四位a的next值,为0,则把a和0下标对应的a进行比较,相同,则第五位b的next值为第四位a的next值加上1,为1,因为是在第四位实现了其next值对应的值与第五位相同。
       5.计算第六位(下标为5)的时候,看第五位b的next值,为1,则把b和1下标对应的b进行比较,相同,则第六位c的next值为第五位b的next值加上1,为2,因为是在第五位实现了其next值对应的值与第五位相同。

代码实现KMP算法:
package test.aglorith;
import java.util.Arrays;
public class KMP {
	//----------------KMP------------------------------
	public void indexByKMP(char[] test,char[] pattern) {
		int test_len=test.length;
		int pattern_len=pattern.length;
		int[] next=getNext(pattern);
		int i=0,j=0;
		while (i<test_len) {
			if (j==pattern_len) {
				System.out.println("配对成功:起始下标(从0开始)为---"+(i-j));
				break;
			}
			if (test[i]==pattern[j]) {
				i++;j++;
			}else {
				if (j==0) {
					i++;j++;
				}else {
					//i=i-j+1;
					j=next[j];
				}
			}
		}
	}
	public int[] getNext(char[] pattern) {
		int pattern_len=pattern.length;
		int[] next=new int[pattern_len];
		next[0]=-1;next[1]=0;
		for (int i = 2; i < pattern_len; i++) {
			int j=i;
			while(j>1) {
				if (pattern[i-1]==pattern[next[j-1]]) {
					next[i]=next[j-1]+1;
					break;
				}else {
					j=next[j-1];
				}
			}
			if (j==1) {
				next[i]=1;
			}
			//System.out.println(Arrays.toString(next));
		}
		System.out.println(Arrays.toString(next));
		return next;
	}
	public static void main(String[] args) {
		char[] test="abcabcabdaaaaa".toCharArray();
		char[] pattern="abcabd".toCharArray();
		KMP kmp=new KMP();
		kmp.getNext(pattern);
		kmp.indexByKMP(test, pattern);
	}
}

至于next函数值的求解原理至今还没有真正想透彻,希望广大网友多多指教!
经网友推荐的博客文章:http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
突然缠绕我心中的那道弯就绕过了,之前在想:
求解T[i]时,T[i-1]与T[next[i-1]]不同时,T[i-1]要与T[next[next[i-1]]]比较;原因是一个词,“比较过了”。还是画图解释(不知道大家看不看得懂):


  • 大小: 79 KB
  • 大小: 56.8 KB
  • 大小: 73.5 KB
2
3
分享到:
评论
4 楼 edr_ 2013-09-27  
wwwcomy 写道
http://news.cnblogs.com/n/176771/

这个比较有帮助 图很好

嗯,讲得很详细!只是我没有具体说next函数值(部分匹配表)的算法。
3 楼 wwwcomy 2013-09-26  
http://news.cnblogs.com/n/176771/

这个比较有帮助 图很好
2 楼 edr_ 2013-09-26  
opqshuai 写道
i=5-5+1=0,错了,应该是1.

额,这个,笔误,画图太粗心了。谢谢啦!
1 楼 opqshuai 2013-09-26  
i=5-5+1=0,错了,应该是1.

相关推荐

    KMP算法算法 KMP算法 KMP

    算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP

    KMP算法详解 KMP算法详解

    KMP算法特别之处在于它可以避免不必要的字符比较,从而在最坏的情况下达到线性时间复杂度O(n),其中n为主串A的长度。 在传统的朴素字符串匹配算法中,当主串与模式串比较到某个位置不匹配时,需要从主串的下一个...

    kmp算法实现

    KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现

    BF算法和KMP算法

    BF 算法和 KMP 算法在字符串匹配中的应用 BF 算法和 KMP 算法是两种常用的字符串匹配算法,分别应用于不同的场景中。本文将对这两种算法进行详细的分析和比较,以便更好地理解它们的原理和应用。 BF 算法 BF ...

    传统KMP算法与改进KMP算法的对比

    KMP算法,全称为Knuth-Morris-Pratt算法,是一种在字符串中寻找子串的高效搜索算法。它由D.E. Knuth、V. Morris和J.H. Pratt三位学者于1970年提出,主要用于解决模式匹配问题。传统的KMP算法避免了不必要的字符比较...

    C++实现的KMP算法

    用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。

    kmp无回溯算法

    北大老师写的kmp无回溯算法,数据结构与算法,大家懂得

    数据结果 kmp算法实验报告

    ### 数据结果 KMP算法实验报告 #### 实验背景与目的 本实验主要针对《数据结构》课程中的字符串处理部分,具体涉及的是模式匹配算法——KMP算法。通过实验加深学生对串类型及其基本操作的理解,并重点掌握两种重要...

    KMP算法Flash演示

    数据结构中KMP算法过程的Flash演示

    Python实现字符串匹配的KMP算法

    kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...

    Kmp算法Java实现源码

    KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。

    KMP算法 严蔚敏版

    此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过

    bf算法和kmp算法及改进的kmp

    给定一个子串,要求找出某个字符串中该子串的第一次出现的位置,即实现各种模式匹配。本资源中含有bf算法,和kmp算法,以及改进后的kmp算法

    KMP算法(C++)示例代码

    KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...

    kmp算法详解及练习

    ### KMP算法详解 #### 一、KMP算法概述 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt三位计算机科学家共同提出。该算法主要用于解决在主...

    kmp算法的代码实现

    数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)

    算法分析与设计KMP算法字符串改进

    《算法分析与设计:KMP算法的字符串匹配优化》 KMP算法,全称为Knuth-Morris-Pratt算法,是计算机科学中一种用于字符串匹配的高效算法。它避免了在进行比较时出现的不必要的回溯,从而显著提高了匹配效率。在给定的...

    KMP算法的实现

    KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的

    串匹配算法——kmp算法,并行算法

    KMP算法是由Knuth、Morris和Pratt三位科学家提出的,是一种高效的精确串匹配算法。它的核心思想是利用模式串的局部匹配信息,通过构建一个“部分匹配表”(next数组或newnext数组)来避免不必要的字符比较,从而减少...

    [C/算法]字符串匹配(BF算法的改进算法:KMP算法和BM算法)

    实现BF算法的改进算法:KMP算法和BM算法; 对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。 附件中 3.3.h BF算法代码 3.5.h KMP算法代码 3.12.h BM算法代码

Global site tag (gtag.js) - Google Analytics