手算KMP匹配的Next值和Nextval值_Sophia_beta的博客-程序员宅基地

技术标签: 算法  数据结构  kmp  

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值,但是如果是考试,那就只能自己来手算这两个数组了,这里分享一下我的计算方法吧。

计算前缀 Next[i] 的值:

我们令 next[0] = -1 。从 next[1] 开始,每求一个字符的 next 值,就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是,这2个"字符串"不能是同一个"字符串")。如果一个都没有,这个字符的 next 值就是0;如果有,就看它有多长,这个字符的 next 值就是它的长度。

计算修正后的 Nextval[i] 值:

我们令 nextval[0] = -1。从 nextval[1] 开始,如果某位(字符)与它 next 值指向的位(字符)相同,则该位的 nextval 值就是指向位的 nextval 值(nextval[i] = nextval[ next[i] ]);如果不同,则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

举个例子:

手算kmp的next和nextval

计算前缀 Next[i] 的值:

next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。

计算修正后的 Nextval[i] 值:

nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0],nextval[1] = next[1] = 0。
nextval[2] = 0;s[2] != s[0],nextval[2] = next[2] = 0。
nextval[3] = -1;s[3] == s[0],nextval[3] = nextval[0] = -1。
nextval[4] = 0;s[4] == s[1],nextval[4] = nextval[1] = 0。
nextval[5] = 0;s[5] == s[2],nextval[5] = nextval[2] = 0。
nextval[6] = -1;s[6] == s[3],nextval[6] = nextval[3] = -1。
nextval[7] = 4;s[7] != s[4],nextval[7] = next[7] = 4。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/cl7689881/article/details/51174422

智能推荐

我的计算机 教案,初中信息技术《初识我的电脑》教案_weixin_39586265的博客-程序员宅基地

初中信息技术《初识我的电脑》教案[教学目标]一、知识性目标1、了解计算机及其应用,认识计算机硬件组成。2、掌握正确的开关机方法和鼠标的基本操作。3、培养学生对计算机的兴趣和正确使用计算机的意识。二、技能目标1、电脑的开关机和鼠标的操作。三、情感目标1、培养学生对今后学电脑的兴趣。[教学重点]1、认识计算机硬件组成。2、掌握正确的开关机方法和鼠标的基本操作。[教学难点]1、硬件与软件的区别。2、双击...

java class list_详解Java 集合类 List 的那些坑_迷茫的公子羽的博客-程序员宅基地

现在的一些高级编程语言都会提供各种开箱即用的数据结构的实现,像 Java 编程语言的集合框架中就提供了各种实现,集合类包含 Map 和 Collection 两个大类,其中 Collection 下面的 List 列表是我们经常使用的集合类之一,很多的业务代码都离不开它,今天就来看看 List 列表的一些坑。第一个坑:Arrays.asList 方法返回的 List 不支持增加、删除操作例如我们执...

使用d3.js动态获取数据文件,并进行垂直柱状图表渲染_xinxiaoyong的博客-程序员宅基地

一、最终效果截图:二、动态返回的原始数据:三、数据描述:本地请求数据的名字:d3-data.csvHTML文件与d3-data.csv文件位置关系:在同一目录级别。本地请求数据的内容:必须一行一条数据。year,population1953,5.941964,6.951982,10.081990,11.342000,12.662010,13.40 数据详情截图:四、代码详情:<!DOCTYPE html><htm...

Windows在局域网内无法访问Linux服务器上的web项目问题_sinat_41351261的博客-程序员宅基地

背景在Linux服务器上部署了一个在Giithub上开源的web项目,一个用ruby写的项目,在Linux服务器上安装了rvm,利用rvm下载ruby环境的各个版本,并用bundle管理下载项目需要的软件包bundle exec rackup项目运行正常,端口号为9292 ,LInux服务器本地可以通过curl http://127.0.0.1:9292正常访问之前在自己电脑的ubuntu系统上部署过这个项目,在本地可以通过http://127.0.0.1:9292进行访问,但是部署到Linu

Java实现判断数据库中是否有某表,如果没有,则执行sql文件创建该表_weixin_44312378的博客-程序员宅基地

public class test { @Test public void test(){ if(isTableExistEntrust("ai_hmst")){ //存在该表执行代码 }else{ RunSql("peple"); } } /** * 运行指定的sql脚本 * @param sqlFileName 需要执行的sql脚本的名字 */ public void RunSql(

WPF快速入门系列(5)——深入解析WPF命令_简单的绿竹的博客-程序员宅基地

http://www.cnblogs.com/zhili/p/WPFCommand.html一、引言  WPF命令相对来说是一个崭新的概念,因为命令对于之前的WinForm根本没有实现这个概念,但是这并不影响我们学习WPF命令,因为设计模式中有命令模式,关于命令模式可以参考我设计模式的博文:http://www.cnblogs.com/zhili/p/Command

随便推点

【pushgateway】shell 脚本获取设备多网口IPv4或IPv6地址,并且推送到pushgateway_张同学 ^_^的博客-程序员宅基地_pushgateway shell脚本

#!/bin/bashinterfaces="eth0 eth1 eth2"function push_data(){ cmd="echo $1 $2 | curl --data-binary @- -g \ http://$s/pushgateway/metrics/job/pushgateway" cmd+="/instance/...

php系统主题,PHPnew助站(简洁式主题管理系统) v1.1_狸花实验室的博客-程序员宅基地

简洁式主题管理系统CMS功能特色:1: 无限分类.2: 三类特色主题显示.3: ubb安全入库,增加特色编辑器.4: 完整功能化后台管理及扩展5: 全站智能缓存.6: 支持多风格及多语言.7: 支持指令管理技术(新增)8: 完美的附件上传机制.9: 过滤系统及tag功能.安装方法:上传root目录中的文件及目录至服务器上, 通过url访问install.php 按顺序安装.初次安装后,第一位注册用...

oracle orion_认识Eclipse Orion:在云端,在云端_cuxiong8996的博客-程序员宅基地

Eclipse Orion项目的目标是在网络中创建一个基于浏览器的开源工具集成平台,该平台完全专注于为Web开发: Orion工具是用JavaScript编写的; 它们在浏览器中运行。 基于Orion浏览器的开发IDE不仅可以在单个浏览器选项卡中运行,而且所有链接都可以工作并且可以共享,从而为开发人员提供了真正的Web开发体验。 Orion组件可由其他项目单独使用(例如Firefox...

CXF_Spring_Rest_??yy的博客-程序员宅基地

一、接口类<PRE class=java name="code">@Path("/rest_HelloWorld")public interface Rest_HelloWorld { @GET @Produces (MediaType.TEXT_PLAIN) @Path("/say/{name}") public String say(@PathPa...

临界区、相关临界区_soldier123333的博客-程序员宅基地_相关临界区

1.概念       临界区:每个进程中访问临界资源的那段代码称为临界区(Critical Section)临界资源:临界资源是一次仅允许一个进程使用的共享资源每次只准许一个进程进入临界区,进入后不允许其他进程进入。不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。相关临界区:多个进程中涉及到同一个临界资源的临界区称为相关临界区。百度百科上对临界

【跃迁之路】【621天】程序员高效学习方法论探索系列(实验阶段378-2018.10.25)..._weixin_34199405的博客-程序员宅基地

@(跃迁之路)专栏实验说明从2017.10.6起,开启这个系列,目标只有一个:探索新的学习方法,实现跃迁式成长实验期2年(2017.10.06 - 2019.10.06)我将以自己为实验对象。我将开源我的学习方法,方法不断更新迭代,全程记录分享实验结束后我将请5位以上资深程序员判断我是否达成目标。本实验旨在探索新方法,所涉...

推荐文章

热门文章

相关标签