`
hao3100590
  • 浏览: 131243 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

KMP算法解析

阅读更多

 

一.理论基础

1.什么是kmp算法

同BF算法一样,就是串的模式匹配算法。

前面已经学过,我想都应该明白BF算法,就是用一种最直观的方式进行模式匹配。

优点:非常容易理解,是我们常用的思维方式来编程;

缺点:效率比较低,在匹配不成功的时候,回朔做了许多无用功;

 

从而根据其缺点,KMP算法就在回朔的时候做了工作,减少其无用功,那么怎么去减少回朔的工作呢?

下面举例说明:

例如:

s = abababc

t = ababc

其匹配过程如下图:


从图中我们看到了具体的变换过程,就是在回朔的过程中做了许多工作,S的i不需要回朔到1,只需要T回朔就可以了,那么怎么知道T回朔到什么位置才好呢?而从上面的图中我们也会发现,其实回朔跟S串是没有关系的,i压根就没变,变的是T的j,故而需要回朔的是T--待匹配模式串,所有回朔的位置是由T串的特点决定的!!当然,就这是问题2,求next数组。

 

2.为什么要求next数组

什么是next数组,简而言之,就是当不匹配的时候,从当前j的位置需要回朔的位置k

如上面的图中,当j=4的时候,回朔的位置是2,故而next[4]=2,这就是next的价值所在:决定在位置j不匹配的时候,回退到位置next[j].

 

3.next如何求之理论基础

既然求next完全是T的事,那么我这里就不像那些书上那样从S去分析,直接切入正题从T分析!书上有时候说的反而有碍思维,要是完全照书,我就不写这些了!

首先实例分析:



 2。代码

 

#include <iostream>
using namespace std;

int strLen(const char *s){
	if(!s) throw "串不能为空!\n";
	int i=0;
	while(*s != '\0'){
		i++;
		s++;
	}
	return i;
}		

/**
	*求next数组值
	*求模式t的next值并存入next数组中
	*t :待求模式数组
	*n :模式数组长度
	*next:next数组
	*/
void getNext(const char* t, int n, int* next){
	int i=0, j=-1;
	next[0] = -1;
	while(i < n){
		//如果j==-1,则回退到了开始位置(只有当开始的时候j才为-1,only one,以后至少都是0)
		//如果相等,匹配,故而向前,此时i的next的值就是j,且存的是最大的j
		if(j == -1 || t[j] == t[i]){
			i++;
			j++;
			next[i]=j;
		}else{//如果不等或j为其他,则j回到next[j]位置继续匹配
			j = next[j];
		}
	}
}

//1.Brute-Force算法(BF算法)
//子串定位(p若属于s,返回串p在s中的位置,否则返回0)
int strIndex(const char* s, const char* p){
	if(!s || !p) throw "串不能为空!\n";
	int i=0, j=0, r = 1;
	int sl = strLen(s);
	int pl = strLen(p);
	if(sl < pl) throw "参数异常,串长度!\n";
	while(i<sl && j<pl){
		if(s[i] == p[j]){
			i++; j++;
		}else{//恢复开始的位置的下一个位置
			i = i-j+1;
			j = 0;
		}
	}
	if(j >= pl) r = i-pl+1;
	else r = -1;
	return r;
}		


//2.KMP算法
//具体的讲解,见博文
int strIndex_kmp(const char* s, const char* p){
	if(!s || !p) throw "串不能为空!\n";
	int i=0, j=0, r = 1;
	int sl = strLen(s);
	int pl = strLen(p);
	if(sl < pl) throw "参数异常,串长度!\n";
		
	//求next
	int *next = new int[pl];
	getNext(p, pl, next);
	cout<<"next数组:";
	for(int j=0; j<pl; j++){
			cout<<next[j]<<" ";	
	}	
	cout<<endl;
	
	while(i<sl && j<pl){
		if(j==-1 || s[i] == p[j]){
			i++; j++;
		}else{//恢复到next[j]
			j = next[j];
		}
	}
	if(j >= pl) r = i-pl+1;
	else r = -1;
	delete next;
	return r;
}

int main(){
	//char a[] = {'a','c','a','b','a','a','b','a','a','b','c','a','c','a','a','b','c','\0'};
	//char b[] = {'a','b','a','a','b','c','\0'};
	char a[] = {'a','b','a','b','a','b','c','\0'};
	char b[] = {'a','b','a','b','c','\0'};
	try{
		cout<<"BF算法:"<<strIndex(a ,b)<<endl;
		cout<<"KMP算法:"<<strIndex_kmp(a, b)<<endl;

	}catch(const char* s){	
		cout<<s<<endl;
	}
}
  • 大小: 29.4 KB
  • 大小: 53 KB
分享到:
评论

相关推荐

    数据结构教学中KMP算法解析.pdf

    此外,KMP算法具有一定的局限性,例如在某些特殊模式串的匹配问题中,可能需要结合其他算法或者对KMP算法本身进行修改才能得到更好的效率。 总的来说,KMP算法是数据结构中字符串匹配领域的一个重要算法,其高效的...

    字符串KMP算法c语言

    ### 字符串KMP算法C语言实现解析 在计算机科学领域,字符串匹配是常见的操作之一,其中KMP算法(Knuth-Morris-Pratt算法)因其高效性而被广泛使用。KMP算法由Donald Knuth、James H.Morris以及Vaughan Pratt共同...

    完全掌握KMP算法思想

    ### 完全掌握KMP算法思想 #### KMP算法概览 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,主要用于在一个文本串中寻找一个模式串的所有出现位置。相较于朴素的字符串匹配算法,KMP算法...

    KMP.rar_KMP_KMP算法_串 KMP算法_字符串匹配

    本文将深入解析KMP算法的原理、实现过程及其在实际应用中的价值。 KMP算法由Donald Knuth、Vaughan Pratt和James H. Morris三位学者于1970年提出,它是一种高效的字符串匹配算法,能在O(n)的时间复杂度内完成字符串...

    kmp算法 编程

    本文将从KMP算法的基本原理、实现细节以及示例代码出发,全面解析KMP算法的精髓。 #### KMP算法的基本原理 KMP算法的核心思想是利用模式串的部分匹配信息来避免重复匹配,从而提高搜索效率。具体而言,KMP算法通过...

    字符串匹配的KMP算法.rar_KMP_KMP算法_kmp 字符串匹配_字符串匹配_文件

    5. www.pudn.com.txt文件可能包含的是KMP算法的实际代码示例或者进一步的解释,文档字符串匹配的KMP算法.doc则可能是详细讲解KMP算法的理论、步骤以及实例解析,供学习者参考。 总的来说,KMP算法是一种高效的字符...

    KMP算法 java版

    接下来,我们将根据提供的Java代码片段来详细解析KMP算法的具体实现。 ```java package com.test.kmp; public class StringMatch { private String S; private String T; // getter 和 setter 方法省略... ...

    kmp算法-基于cuda实现kmp算法.zip

    以下是对KMP算法和CUDA实现的详细解析: 1. **KMP算法原理**: KMP算法的核心是构造一个部分匹配表,这个表记录了模式串中每个字符之前最长的公共前后缀长度。当模式串在文本串中比较时,如果遇到不匹配的情况,...

    kmp算法步骤解析.md

    kmp算法

    使用c编写KMP算法,可以完美运行

    ### 使用C语言实现KMP算法 #### 知识点概览 本文将详细介绍如何使用C语言来实现KMP(Knuth-Morris-Pratt)算法,并通过提供的代码示例进行解释。KMP算法是一种高效的字符串匹配算法,它可以避免在模式匹配过程中...

    kmp算法-基于Java实现kmp字符串搜索算法.zip

    本文将详细介绍KMP算法的原理,并以Java语言为例,解析其实现过程。 1. KMP算法概述: KMP算法的核心思想是避免对已匹配的字符进行不必要的比较,通过预处理模式串来创建一个“部分匹配表”,用于指导在主串中遇到...

    kmp基本算法演示.rar

    《深入理解KMP算法:基于易语言的实现与解析》 KMP(Knuth-Morris-Pratt)算法,一种在字符串中查找子串的高效算法,由唐纳德·克努斯、詹姆斯·莫里斯和弗雷德里克·普拉特三位学者于1970年提出。其主要解决了在主...

    数据结构BF和KMP算法

    ### 数据结构中的BF和KMP算法 #### BF(Brute Force)算法 BF算法是一种简单的字符串匹配算法,也称为暴力匹配算法。其基本思想是将模式串T在主串S中从头开始逐个字符比较,若匹配成功则返回位置,否则继续下一轮...

    KMP算法介绍.pdf

    #### 五、KMP算法实例解析 以题目中给出的例子为例,假设主串A="abababaababacb",模式串B="ababacb",下面展示具体的匹配过程: 1. **初始化阶段**: - 主串A的索引i=0,模式串B的索引j=0; - 初始化`next`数组...

    文学研究助手(字符串的查找\模式匹配\KMP算法)

    《文学研究助手——深入解析KMP算法在字符串查找与模式匹配中的应用》 在文学研究领域,高效地处理文本信息是至关重要的。本项目“文学研究助手”正是为解决这一问题而设计,它利用C语言实现,核心算法是著名的KMP...

    数据结构-KMP算法原理

    ### 数据结构-KMP算法原理 #### 一、引言 KMP算法(Knuth-Morris-Pratt算法)是一种在文本中查找模式串的高效算法,由Donald Knuth、James H. Morris和Vaughan Pratt三人共同提出。与传统的暴力匹配(如Boyer-...

    KMP改进算法

    改进后的KMP算法在诸如文本搜索、文件路径匹配、正则表达式解析等领域有着广泛的应用。例如,当在大量文件名中寻找符合特定模式(如`*.txt`)的文件时,改进的KMP算法能有效提升查找效率。 总结,KMP改进算法通过...

    关于数据结构中的kmp算法详解

    本文将深入解析KMP算法的原理,并通过实例演示其执行过程,旨在为初学者提供一个清晰的学习路径。 #### KMP算法的核心思想 KMP算法的核心在于利用模式串自身的部分匹配信息来避免不必要的比较。在传统的模式匹配...

    kmp算法要点和难点具体应用场景.zip

    《KMP算法要点和难点:具体应用场景》 KMP(Knuth-Morris-Pratt)算法是一种在字符串中查找子串出现位置的高效算法,由Donald Knuth、James H. Morris和 Vaughan Pratt三位学者于1970年提出。这个算法避免了在主串...

    易语言源码KMP算法模块源码.rar

    《易语言KMP算法模块源码解析》 易语言,作为中国本土开发的一款特色编程语言,以其独特的中文编程界面和简单易学的特点,受到了许多初学者的欢迎。本篇文章将聚焦于易语言中的一个核心算法模块——KMP(Knuth-...

Global site tag (gtag.js) - Google Analytics