文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > BF与kmp算法分析
侵权投诉

BF与kmp算法分析

本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同。下文分别 从最简单的前缀蛮力匹配算法和后缀蛮力匹配算法入手,详细的介绍KMP算法和BM算法以及它们的实现。
KMP算法
首先来看一下前缀蛮力匹配算法的代码(以下代码从linux源码string.h中抠出),模式串和母串的比较是从左到右进行(strncmp()),如果找不到和模式串相同的子串,则从左到右移动模式串,距离为1(s++)。

1
char * strstr(register const char *s, register const char *wanted)
2
{
3
register const size_t len = strlen(wanted);
4
if (len == 0) return (char *)s;
5
while (*s != *wanted || strncmp(s, wanted, len))
6
if (*s++ == '\0')
7
return (char *)NULL;
8
return (char *)s;
9
}
KMP算法中的KMP分别是指三个人名:Knuth、Morris、Pratt,其本质也是前缀匹配算法,对比前缀蛮力匹配算法,区别在于它会动态 调整每次模式串的移动距离,而不仅仅是加一,从而加快匹配过程。下图通过一个直观的例子展示前缀蛮力匹配算法和KMP算法的区别,前文提过,这二者唯一的 不同在于模式串移动距离。


上图中,前缀蛮力匹配算法发现匹配不上,就向右移动距离1,而KMP算法根据已经比较过的前缀信息,了解到应该移动距离为2;换句话说针对母串的下一个匹配字符,KMP算法了解它下回应 该匹配模式串的哪个位置,比如上图中,针对母串的第i+1个字符,KMP算法了解它应该匹配模式串的第k+1个字符。为什么会是这样,这是因为母串的子串 T[i-k, i]=aba,而模式串的子串P[0,k]=aba,这二者正好相等。所以模式串应该移动到这个位置,从而让母串的第i+1个字符和模式串的第k+1个字 符继续比较。

那k值又是如何寻找?请注意上图中,模式串位置j已经匹配上母串的位置i,也就是T[i-k, i] = P[j-k, j]=aba;根据前文的T[i-k, i] = P[0, k] = aba, 从而得出P[0, k] = P[j-k, j] = aba。通过观察发现,就是在模式的子串[0, j]中寻找一个最长前缀[0,k],从而使得[j-k, j] = [0,k];
于是可以定义一个jump数组,jump[j]=k,表示满足P[0, k] ==P[j-k, j] 的最大k值,或者表述为:如果模式串j+1匹配不上母串的i+1,那跳转到模式串k+1继续比较。有了这个jump数组,就很容易写出kmp算法的伪代码:

01
j:=0;
02
for i:=1 to n do
03
Begin
04
while (j>0) and (P[j+1]<>T[i]) do j:=jump[j];[
05
if P[j+1]=T[i] then j:=j+1;
06
if j=m then
07
Begin

第1页

你可能喜欢

热门文档

相关文档

  • BF算法与KMP算法

    BF算法与KMP算法_计算机软件及应用_IT/计算机_专业资料。BF算法与KMP算法,附带...【②问题分析】 【③算法设计】 【④算法实现】 #include <stdio.h> #...

  • BF算法和KMP算法

    BF算法和KMP算法_计算机软件及应用_IT/计算机_专业资料。KMP 算法的原理及实现...(请结合下 文源代码看这里的分析) 下面解释一下 next 数组的含义,这个也是 ...

  • BF和KMP算法

    相对于 BF 算法来说,KMP 移动 更多的位数,起到了一个加速的作用! 三、 BF&KMP 算法性能分析 BF 算法的时间复杂度 O(strlen(S) * strlen(T)),空间复杂度...

  • KMP算法分析 算法设计

    计算机算法设计与分析 KMP 算法分析王法金(安徽中医学院,医药信息工程学院,安徽 ...在大多数情况下, KMP算法并不比BF算法好很多, 但KMP算法确 保了线性, 并且...

  • BF算法和KMP算法代码

    BF算法和KMP算法代码_IT/计算机_专业资料。BF算法和KMP算法代码BF 算法 #include<iostream> #include<string.h> using namespace std; #define N 80 void main...

  • BF算法和KMP算法程序

    实验内容: 比较 BF 算法和 KMP 算法的优劣 实验基本要求: 1.采用定长顺序显示表示串长的结构来存储串 2.实现 BF 算法(即朴素算法),BF 函数头如下 int Index...

  • BF算法、KMP算法、BM算法

    BF算法、KMP算法、BM算法_专业资料。BF算法、KMP算法、BM昆明理工大学信息工程与自动化学院学生实验报告( 2010 — 2011 课程名称: 课程名称: 算法分析与设计 ...

  • 串的模式匹配算法:BF和 KMP算法

    串的模式匹配算法:BF和 KMP算法_信息与通信_工程科技_专业资料。数据结构 串... 2014教师资格材料分析辅... 2014小学教师资格考试《... 2014年幼儿园教师资格...

  • 字符串模式匹配算法--BF & KMP算法

    二、BF 算法(简单匹配算法) Brute-Force 简称 BF 算法,亦称为简单匹配算法。...KMP 算法思想:分析模式串 s,求的模式串的部分匹配信息,用 next 数组保存。KMP...

  • KMP算法-如何理解

    KMP算法-如何理解_计算机软件及应用_IT/计算机_...要理解 next[j]=k 中,k 的含意; (1)BF 算法... 2014教师资格材料分析辅... 2014小学教师资格考试...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email