小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

KMP算法的简单理解

2018年11月27日 1913点热度 0人点赞 0条评论

总结一些在网上看到的关于KMP算法的简单理解,目前我的理解还很初步,很多东西还似懂非懂,目前先贴下来,期待以后慢慢懂。

KMP算法的基本原理

假设字符串S=BBC ABCDAB ABCDABCDABDE,搜索词P=ABCDABD。那么我们在执行搜索的时候进行下面的操作:

首先,字符串“BBC ABCDAB ABCDABCDABDE”的第一个字符与“ABCDABD”的第一个字符比较,因为不匹配,所以搜索词后移一位,直到移动到匹配的地方,即

B B C A B C D A B A B C D A B C D A B D E
A

然后我们就发现匹配了,于是开始使用搜索词P的第二个字符与字符串S下一个字符进行比较发现相匹配,然后继续比较……直到P的最后一个字符D与S中相应位置进行比较,发现S中为空格,即

B B C A B C D A B A B C D A B C D A B D E
A B C D A B D

如果是传统的方法,则是将字符串P的指针回到第一个字符,然后后移继续进行比较。这样的方法是暴力方法,复杂度太高。KMP算法是利用了已经知道的匹配信息,然后不再把“搜索位置”移回已经比较的位置再进行比较,而是继续往后移。这里利用的就是部分匹配值(Partial Match Value)。

部分匹配值的介绍

首先要了解“前缀”和“后缀”的概念。前缀是指除了最后一个字符以外,一个字符串的全部头部的集合,后缀是指除了第一个字符以外,一个字符串的全部尾部的集合。所谓部分匹配值就是前缀和后缀的最长的共有元素的长度。以ABCDABD为例,有以下情况:

字符 前缀 后缀 共有元素长度
A - - 0
AB A B 0
ABC A/AB BC/C 0
ABCD A/AB/ABC BCD/CD/D 0
ABCDA A/AB/ABC/ABCD BCDA/CDA/DA/A 1
ABCDAB A/AB/ABC/ABCD/ABCDA BCDAB/CDAB/DAB/AB/B 2
ABCDABD A/AB/ABC/ABCD/ABCDA/ABCDB BCDABD/CDABD/DABD/ABD/BD/D 0

所谓部分匹配,实质上指的是有时字符串头部和尾部会有重复。例如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

我们进行“继续往后移”的移动位数的标准是用如下公式计算:

移动位数=已匹配的字符数-对应的部分匹配值

基于上面这个公式,我们可以看到,已匹配的字符数为6(ABCDAB),对应的部分匹配值为2,那么就将搜索词向后移动4位。如下所示:

B B C A B C D A B A B C D A B C D A B D E
A B C D A B D

依旧是如此,可以看到空格与C不匹配,搜索词还要继续往后移。此时已匹配的字符数为2(AB),对应的部分匹配值为0,所以往后移动2位。

B B C A B C D A B A B C D A B C D A B D E
A B C D A B D

此时空格与A不匹配,往后继续移动1位,得到如下所示。

B B C A B C D A B A B C D A B C D A B D E
  A B C D A B D

这个时候发现D又不匹配,此时已匹配的字符数为6位,对应的部分匹配值为2,所以向右移动4位,得到如下所示。

B B C A B C D A B A B C D A B C D A B D E
  A B C D A B D

此时,发现匹配,搜索完成。当然,如果想继续寻找后面是否还会有继续匹配的,可以继续移动7位(已匹配的字符数为7,对应的部分匹配值为0)。

我们换个角度来理解,假设P为主字串,而T为子串。当匹配失败时,j要移动的下一个位置k。存在着这样的性质:最前面的k个字符和j之前的最后k个字符是一样的。即

P[0 ~ k-1] == P[j-k ~ j-1]

因为:

当T[i] != P[j]时,有T[i-j ~ i-1] == P[0 ~ j-1],由P[0 ~ k-1] == P[j-k ~ j-1],必然:T[i-k ~ i-1] == P[0 ~ k-1]。

next数组的求解思路

讲完上面的原理,下面就是编程的实现,这里面最重要的就是根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。

实际上,next[j]的值(也就是k)表示,当P[j] != T[i]时,j指针的下一步移动位置。

我们在做题的时候来求next数组,可以通过手算,按照计算部分匹配值即可。要注意的是,next[1]=0,next[1]=1,next[n]是计算前面n-1个字符的部分匹配值,如果找到,那么next值是该长度加1,否则next值是1(其实就是0+1)。

但是,编写程序我们需要原理。如图2所示。此时j=0,如果这个时候不匹配,那么j已经在最左边,不可能移动了,所以这个时候应该是i来移动,所next[0]=-1。

图1

当j=1的时候,按照前面说的,我们应该将j移动到为T[0]的位置,所以实际上这里next[1]=0。

图2

对比图3中的两个图,我们发现当P[k] == P[j]时,有next[j+1] == next[j] + 1。其实这个是可以证明的:因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。(next[j] == k)这时候现有P[k] == P[j],我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。即:P[0 ~ k] == P[j-k ~ j],即next[j+1] == k + 1 == next[j] + 1。(这里还需要多去理解理解)

图3

如果P[k] != P[j],那么k=next[k],如图4所示。

图4

nextval数组的求解思路

nextval[i]的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致,如果一致则用s[next[i]]的nextval的值作为nextval[i],如果不一致,则用next[i]做为nextval[i]。

即以下格式:

nextval[i] = s[next[i]]==s[i]?nextval[s[next[i]]]:next[i]

KMP算法的代码

KMP算法:可以实现复杂度为O(m+n)

#include<stdio.h>
#include<string.h>
void getNext(const char P[], int next[])
{
	int q, k;
	int m = strlen(P);
	next[0] = 0;
	for (q = 1, k = 0; q < m; ++q)
	{
		while (k > 0 && P[q] != P[k])
			k = next[k - 1];
		if (P[q] == P[k])
		{
			k++;
		}
		next[q] = k;
	}
}
int kmp(const char T[], const char P[], int next[])
{
	int n, m;
	int i, q;
	n = strlen(T);
	m = strlen(P);
	getNext(P, next);
	for (i = 0, q = 0; i < n; ++i)
	{
		while (q > 0 && P[q] != T[i])
			q = next[q - 1];
		if (P[q] == T[i])
		{
			q++;
		}
		if (q == m) // 输出找到的位置  还可以判断i == n - 1 未找到
		{
			printf("Pattern occurs with shift:%d\n", (i - m + 1));
		}
	}
}

int main()
{
	int i;
	int next[100] = { 0 };
	char T[20], P[20];
	scanf("%s%s", T, P);

	printf("%s\n", T);
	printf("%s\n", P);
	kmp(T, P, next);
	for (i = 0; i < strlen(P); ++i)
	{
		printf("%d ", next[i]);
	}
	printf("\n");
	return 0;
}

 

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: KMP 数据结构
最后更新:2018年11月27日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
《Python语言程序设计基础》课后习题程序整理(第2~4章) WordPress代码高亮插件SyntaxHighlighter终极使用详解 想家(2010 S.V Beijing Travel ARTICE) 《我们在一中的日子》正式发布 子进程的产生与回收(fork与waitpid) 雪天随想
标签聚合
Java leetcode 高中 鸟哥的linux私房菜 学习 python学习 生活 算法 linux Python
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号