4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

时间：2022-09-22 21:32:08

课本源码部分

第4章  串 - KMP匹配算法

——《数据结构》-严蔚敏.吴伟民版

       源码使用说明  链接☛☛☛ 《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明

       课本源码合辑  链接☛☛☛ 《数据结构》课本源码合辑

       习题集全解析  链接☛☛☛ 《数据结构题集》习题解析合辑

       本源码引入的文件  链接☛ SequenceString.c

      文档中源码及测试数据存放目录：数据结构\▲课本算法实现\▲04 串\04 KMP

概述

       KMP匹配算法是普通匹配算法的改进，它提高了串匹配过程中的效率。

解析

       KMP匹配算法的重点在于利用模式串自身的重复部分，在匹配中消除那些重复的匹配过程。如下图，当模式串匹配与主串在Si和Pj处失配时，此时如果模式串的两个黄色区域重复，那么只需将模式串右移一定位置，让主串的黄色区域与模式串的第一个黄色区域做比较即可。也就是说，Pj处失配后，只需让主串的Si与Pk继续比较，而不必退回到P1处。KMP算法就是用来计算模式串某个字符处失配后，应该退回的下一个用来比较的字符位置。

       匹配算法如下图：

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

源码

       文件一 ☛  KMP.h 

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

       文件二 ☛  KMP.c 

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

       文件三 ☛  KMP-main.c （测试文档）

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

测试结果展示

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

       更多章节持续更新中...4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版

4-4-串的KMP匹配算法-串-第4章-《数据结构》课本源码-严蔚敏吴伟民版的更多相关文章

  1. KMP 解决串的模式匹配问题

    初学KMP的时候,一直不得要领.后来学习AC自动机的时候,一下子明白了KMP实际上是AC自动机的特殊情况. 首先贴三段代码,一组是回溯法,暴力求解,另外两个是KMP串模式匹配 /* 回溯法字符串匹配算 ...

  2. 《数据结构》之串的模式匹配算法——KMP算法

    //串的模式匹配算法 //KMP算法,时间复杂度为O(n+m) #include <iostream> #include <string> #include <cstri ...

  3. 数据结构- 串的模式匹配算法：BF和 KMP算法

      数据结构- 串的模式匹配算法:BF和 KMP算法  Brute-Force算法的思想 1．BF(Brute-Force)算法 Brute-Force算法的基本思想是: 1) 从目标串s 的第一个字 ...

  4. 【算法】串的模式匹配算法（KMP）

    串的模式匹配算法     问题:         求子串位置的定位函数如何写? int index(SString S,SString T,int pos);         给定串S,子串T,问T在 ...

  5. 串的模式匹配算法 ------ KMP算法

    //KMP串的模式匹配算法 #include <stdio.h> #include <stdlib.h> #include <string.h> int* get_ ...

  6. 串、串的模式匹配算法（子串查找）BF算法、KMP算法

    串的定长顺序存储#define MAXSTRLEN 255,//超出这个长度则超出部分被舍去,称为截断 串的模式匹配: 串的定义:0个或多个字符组成的有限序列S = 'a1a2a3…….an ' n ...

  7. 【Java】 大话数据结构&lpar;8&rpar; 串的模式匹配算法（朴素、KMP、改进算法）

    本文根据<大话数据结构>一书,实现了Java版的串的朴素模式匹配算法.KMP模式匹配算法.KMP模式匹配算法的改进算法. 1.朴素的模式匹配算法 为主串和子串分别定义指针i,j. (1)当 ...

  8. &lbrack;从今天开始修炼数据结构&rsqb;串、KMP模式匹配算法

    [从今天开始修炼数据结构]基本概念 [从今天开始修炼数据结构]线性表及其实现以及实现有Itertor的ArrayList和LinkedList [从今天开始修炼数据结构]栈.斐波那契数列.逆波兰四则运 ...

  9. 串、KMP模式匹配算法

    串是由0个或者多个字符组成的有限序列,又名叫字符串. 串的比较: 串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号. 计算机中常用的ASCII编码,由8位二进制 ...

随机推荐

  1. 使用iptables防火墙限制web的访问PV

    使用iptables防火墙限制web的访问PV #!/bin/bash while true;do awk '{print $1}' /tmp/test/access.log| grep -v &qu ...

  2. How to setup SVN&quest;

    2014-01-08 11:43:50 如何简单设置SVN(前提是SVN已经安装) 1. 创建一个目录: mkdir -p ~/svn/2.1.J.1.1 2. 进入新创建的目录: cd svn/2. ...

  3. 2&period;MySQL入门基本操作初体验

    启动和关闭mysql服务器: 一.启动方式 1.使用 mysqld 脚本启动:/etc/inint.d/mysqld start 2.使用 守护进程safe_mysqld 启动:safe_mysqld ...

  4. Unity 制作RPG小地图

    效果图: 最近公司要制作小地图,搜索网上的文章没找到有什么小实例,=.=直接上步骤: 制作小地图步骤: 1. 人物头顶有一个面板呈现人物图标 2. 有一个摄像机在主角头顶!(Target Textur ...

  5. MySQL数据类型转换函数CAST与CONVERT的用法

    MySQL 的CAST()和CONVERT()函数可用来获取一个类型的值,并产生另一个类型的值.两者具体的语法如下: 1.CAST(value as type) 就是CAST(xxx AS 类型) 2 ...

  6. 30&period;Django CSRF 中间件

    CSRF 1.概述 CSRF(Cross Site Request Forgery)跨站点伪造请求,举例来讲,某个恶意的网站上有一个指向你的网站的链接,如果某个用户已经登录到你的网站上了,那么当这个用 ...

  7. Javascrip 入门第三节课

    一.location对象 location.href 获取当前网页的URLlocation.search() 获取?之后的请求信息 location.href="URL" // 跳 ...

  8. Linux上使用源代码安装软件

  9. sql-server的添加数据库文件（日志数据）以及收缩数据库文件（日志数据）

    环境: SSMS sql-server2016 一.为数据库添加数据文件 添加日志数据文件 以下是添加数据文件和日志文件的代码 ALTER DATABASE [joinbest] ADD FILE ( ...

  10. QT&plus;VS2013 1配置和安装

    相关参考:http://www.cnblogs.com/ranjiewen/p/5318768.html 1下载 VS2013 微软官网查找  https://www.visualstudio.com ...

相关文章