龙空技术网

10张图:把 KMP 拿捏住,按在地上摩擦

木节学编程 199

前言:

当前姐妹们对“kmp算法的时间复杂度三维图”大概比较注意,姐妹们都想要学习一些“kmp算法的时间复杂度三维图”的相关内容。那么小编也在网上汇集了一些有关“kmp算法的时间复杂度三维图””的相关资讯,希望你们能喜欢,咱们一起来了解一下吧!

小伙伴们好久不见,今天将开设“数据结构与算法”专栏,一起梳理一遍硬核课程的重要知识点,那我们开始吧

正文

字符串匹配是计算机的基本任务之一,举个例子,有一个字符串“aaaaaaca",我想知道里面是否包含另一个字符串“aaaac”,该怎么办?

这里就会使用到串的模式匹配算法,最常见的分别是传统的Brute-Force(暴力)算法KMP算法

BF算法设计思想

1、主串和模式串逐个字符进行比较

2、当出现字符串不相同时,也就是失配时,主串的比较位置重置为起始位置的下一个字符位置,模式串的比较位置重置为起始位置

3、匹配成功后返回主串中匹配串的起始位置,否则就返回错误代码

BF算法的设计缺陷及解决方案

在BF算法中,每次失配都需要回溯指向上次比较起始字符的下一个字符。通过观察发现:在回溯的时候,已匹配似乎有一部分没必要继续比较了,这样可以降低算法的时间复杂度

KMP算法的出现有效地解决了BF算法的缺陷。KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的。

但是这种算法相对于BF算法不太容易理解,网上也有很多解释,但配图有点少,总感觉差点意思,下面我通过画图的方式详细介绍KMP算法的设计思想和工作原理

KMP算法设计思想

在匹配过程中出现字符比较不相等时,主串 S已比较的位置不回溯,模式串 T比较的位置进行移动

在匹配过程中有一个难题需要解决:如何计算模式串 T失配时的移动位数?经过三位牛人的研究,设计出了部分匹配函数

部分匹配函数

部分匹配函数是KMP算法中最难以理解的部分。首先需要理解前缀后缀最大共有长度的概念。

· 前缀:指除了最后一个字符以外,一个字符串的全部头部组合

· 后缀:指除了第一个字符以外,一个字符串的全部尾部组合

· 最大共有长度(部分匹配值):指前缀和后缀中的最大共有元素,没有则为0。例如“abab”的前缀为“a”、“ab”、“aba”,后缀为“b”、“ab”、“bab”,最大共有元素为“ab”,所以最大共有长度为 2

回顾一下KMP算法的匹配过程:

红线框出的部分恰好就是失配时已匹配部分,“aaaa” 的最大共有元素为 “aaa”,这一部分字符就是不需要再重复进行比较直接跳过的字符

在代码实现过程中,j 移动后的位置 = 模式串 T 的起始位置下标 + 部分匹配值。通常起始下标为 0,因此 j 移动后位置 = 部分匹配值,即 j = next[j],next[j] 就是部分匹配函数,j 为失配时的位置

因此接下来就成了对部分匹配函数的是实现。将 “aaaac” 以首字符起始的所有子串的最大共有长度枚举出来,构成部分匹配表,它描述了失配时的下标 j 与部分匹配值的关系

部分匹配表则是通过模式串 T 的自匹配实现:

示例代码(C语言哦):

/*KMP匹配算法*/int KMPCompare(HString parent, HString child, intpos) { int next[255]; Get_Next(child, next); int i = pos - 1; int j = 0;     //j用于子串child中的起始位置 while (i < parent.length && j < child.length) {  if (j == 0 || parent.ch[i] == child.ch[j]) {   ++i;   ++j;  }  else {   j = next[j];    //i不变,j后退  } } if (j == child.length) {  return (i + 1) - j; } return 0;}/*部分匹配函数的实现*/void Get_Next(HString child, int * next) { int i = 0; int j = -1; next[0] = -1;   //不会用到 while (i < child.length) {  if (j == -1 || child.ch[i] == child.ch[j]) {   ++i;   ++j;   next[i] = j;  }  else {   j = next[j];  } }}void main() { /*使用KMP算法匹配串*/ HString parent, child; StrAssign_HeapString(&parent, "BBC ABCDAB ABCDABCDABDE"); StrAssign_HeapString(&child, "ABCDABD"); printf("Index = %d\n", KMPCompare(parent, child, 1));}

关注即可提高学习效率!我是木节,下期再见!

标签: #kmp算法的时间复杂度三维图 #kmp算法考试题 #kmp算法移动例子 #kmp和bf算法 #bf算法和kmp算法