kmp算法的基本总结

2024-08-28 21:58
文章标签 算法 总结 基本 kmp

本文主要是介绍kmp算法的基本总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

字符串的快速匹配kmp算法
1,朴素的模式匹配算法

目标串      T            t0  t1  t2  t3   t4  t5   t6  t7   t8  t9……
模式串      pat         p0 p1 p2 p3  p4 p5  p6 p7  p8 p9……
如果t0=p0,t1=p1,t2=p2   tm-1=pm-1,则字符串匹配成功,否则将pat串后移一位
形成
     
目标串      T            t0  t1  t2  t3   t4  t5   t6  t7   t8  t9……
模式串      pat              p0 p1 p2 p3  p4 p5  p6 p7  p8 p9……
再次进行匹配判断,失败再后移一位,如果tn-1和pm-1不相等,则匹配结束,返回不存在目标串中不含有字串
 

这种匹配算法是带回溯的算法,一旦比较不相等,就将模式串pat后移一位,从p0开始判断,设目标串的长度为n,匹配串的长度为m,第一趟失败比较m次,第二趟失败又比较m次,依次下去,最坏的情况是比较n-m+1次,在多数的情况下m是远小于n的,所以可以认为算法的时间复杂度是O(m*n)。由此我们引入一种不回溯的匹配算法,提高匹配的效率。



2改进的算法kmp算法

我们给出目标串味T abbaba,模式串为aba
根据朴素算法匹配为

T a b b a b a
P a b a
我们可以看到第一趟t0=p0,t1=p1,t2!=p2;但是p0!=t1;由此可以推断t1=p1!=p0,将P右移一位用t1和p0比较是肯定不相等的,没必要再进行了,p0=p2,所以同样p0!=t2;这一趟也不用比较,我们应该直接将P向右移动3位,直接用t3和p0进行比较,这样匹配就消除了回溯,这就是kmp算法的思想


一般情况 T=“t0t1t2t3t4……tn-1”,模式P="p0p1p2p3pn-1",根据1中的朴素匹配算法可以得到从目标串T的第s个位置ts与模式串的第0个位置进行比较,直到在目标T第s+j位置t(s+j)处失配


这是,可以得到  t(s)t(s+1)t(s+2)t(s+3)……t(s+j-1)=p0p1p2p3……p(j-1)              (x)
那么下一趟应该从目标T中第(s+1)个位置开始匹配
若想成功则有,p0p1p2p3……P(m-1)=t(s+1)t(s+2)t(s+3)………t(s+m);
如果在模式串P中p0p1p2p3……p(j-2)  !=   p1p2p3……p(j-1);                                (y)
则第s+1趟不用比较了
因为由xy式可以得到 p0p1p2p3……p(j-2)  !=t(s+1)t(s+2)t(s+3)……t(s+j-1)

那么第s+2趟呢,
我们要判断一下p0p1p2……p(j-3)与p2p3……P(j-1)的关系。
如果p0p1p2……p(j-3)   !=    p2p3……P(j-1)
仍有
p0p1p2p3……P(j-3)   !=   t(s+2)t(s+3)……t(s+j-1)
这一趟没必要
我们以此类推直到有一个k使p0p1……p(k+1)   !=  p(j-k-2)(j-k-1)……p(j-1)
                                             p0p1……p(k)   =  p(j-k-1)(j0k)……p(j-1)

才有p0p1……p(k)  =  t(s+j-k-1)t(s+j-k)……t(s+j-1)
                                   p(j-k-1)   p(j-k)  ……p(j-1)
这时模式串p已经向后滑动了j-k-1位,因此可以直接从t中的t(s+j)与模式中的p(k+1)开始,继续向下比较。


这个算法中,目标T在第s趟比较失配后,指针s不必回溯,算法下一趟从此开始向下进行比较,而在模式p中,扫描指针p应退回到p(k+1)处
对于不同的j值,k值只依赖与模式p本身的前j个字符的构成。因此我们可以用一个next数组来表示
设模式P=p0p1p2p3……pm-2pm-1,则next数组的取值如下

                       -1(j=0)时
next(j)  =        k+1当0<=k<j-1时,且使的p0p1……p(k)=p(j-k-1)p(j-k)……p(j-1)
                      0其它情况
p=abaabcac

j             0      1        2       3      4      5       6         7     
p            a     b        a        a     b      c       a         c
next(j)    -1    0       0        1      1      2       0         1

下面是用kmp算法实现的匹配代码

<span style="font-size:18px;">int  fastfind(char  *s,char *str,int next[])//s为目标串,str为匹配串
{
int  p=0;
int t=-1;
int lent=strlnen(s);
int lenp=strlen(str);
while(p<lenp&&t<lent)
{
if(p==-1||str[p]==s[t])
{
p++;
t++;
}
else
{
p=next[p];
}
}
if(p<lenp)
return -1;//匹配失败
else
return t=lenp;//匹配成功
}</span>

时间复杂度取决于while循环,因为无回溯,最多比较lent次,时间复杂度为O(lent)。


那么问题来了,我们如何得到next数组。
我们可以用递推的方法得到next数组;设next(j)=k;
则0<=k<j-1且p0p1……pk=p(j-k-1)p(j-k)……p(j-1)
若设next(j+1)=max{k+1|0《=k+1<j},使得p0p1……p(k=1)=p(j-k-1)p(j-k)……p(j)成立
若p(k+1)=p(j),next(j+1)=k+1=next(j)+1;
若p(k+1) != p(j),在p0p1p2……pk中存在p0p1……ph = p(k-h)p(k-h+1)……p(k);
1  存在h值
next(k)=h;
p0p1……ph = p(k-h)p(k-h+1)……p(k) = p(j-h-1)p(j-h)……p(j-1)
如果p(h+1)=p(j)
next(j+1)=h+1=next(k)+1=next(next(j))+1;
否则在p0p1……ph中寻找更小的值,next(h)=t;以此下去,直到next(t)=-1,失败
求next数组代码
void getnext(int next[],char *str)
{
int j=0;
int k=-1;
int lenp=strlen(str);
next[0]=-1;
while(j<lenp)
{
if(k==-1||str[k]==str[j])
{
k++;
j++;
next[j]=k;
}
else
k=netx[k];
}
}

时间复杂度为O(lenp);总的时间复杂度为O(lenp+lent).

参考数据结构书


这篇关于kmp算法的基本总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116001

相关文章

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

Python中多线程和多进程的基本用法详解

《Python中多线程和多进程的基本用法详解》这篇文章介绍了Python中多线程和多进程的相关知识,包括并发编程的优势,多线程和多进程的概念、适用场景、示例代码,线程池和进程池的使用,以及如何选择合适... 目录引言一、并发编程的主要优势二、python的多线程(Threading)1. 什么是多线程?2.