没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义kmp算法演示

kmp算法演示

kmp算法

需积分: 50 11 下载量 32 浏览量 2018-11-20 17:02:59 上传评论 2 收藏 283KB PPT 举报

温馨提示

试读

33页

kmp算法求Next值演示，可以自己多研究一下，上面详细的讲解了KMP算法求Next值的具体方法

资源详情

资源评论

KMP 算法

一、朴素的字符串匹配



我们可以写出很容易实现的字符串匹配的算

法，从 A 的起始位置和 B 的起始位置开始比

较，如果匹配不成功则从 A 原先起始位置的

下一位开始和 B 的起始位置开始比较。



如果 A 和 B 的字符个数分别是 m 和 n ，那

么这个算法的效率是 O(mn) ，虽然大部分

情况下不至于 m*n 次但还是有很多不幸的

情况发生。

一、朴素的字符串匹配



设

A=“aaaaaaaaaaaaaaaaaaaaaaaaaaaaa

aaab”

B=“aaaaaaaab”

按照朴素算法，每次比到 B 的最后一位发现

不同又要重新从 B 的开头和 A 的下一个字符

开始比较。

一、朴素的字符串匹配



朴素算法中不可避免的存在“回溯”现象，因

此降低了算法的效率，下面介绍的是一种最

坏情况下 O(n) 的算法（这里假设 m<=n

），即传说中的 KMP 算法。

二、ＫＭＰ算法概述



KMP 算法是用来处理字符串匹配的。换句

话说，给你两个字符串，你需要回答， B 串

是否是 A 串的子串（ A 串是否包含 B 串）

。例如” Today is Tuesday”. 中是否包

含” day” ，在哪些位置包含。



这个算法是由 Knuth 、 Morris 、 Pratt 三

个提出来的，取了这三个人的名字的头一个

字母。

剩余32页未读，继续阅读

评论收藏

内容反馈

最新资源

(175128050)c&c++课程设计-图书管理系统
视频美学多任务学习中PyTorch的多回归实现-含代码及解释
基于ssh员工管理系统
5G SRM815模组原理框图.jpg
T型3电平逆变器，lcl滤波器滤波器参数计算，半导体损耗计算，逆变电感参数设计损耗计算 mathcad格式输出，方便修改同时支持plecs损耗仿真，基于plecs的闭环仿真，电压外环，电流内环
毒舌（解锁版）.apk
显示HEX、S19、Bin、VBF等其他汽车制造商特定的文件格式
操作系统实验 Ucore lab5
8bit逐次逼近型SAR ADC电路设计成品入门时期的第三款sarADC，适合新手学习等包括电路文件和详细设计文档 smic0.18工艺，单端结构，3.3V供电整体采样率500k，可实现基
操作系统实验 ucorelab4内核线程管理