KMP算法:next和nextval值计算
2024-10-19 08:55:49
KMP算法的next和nextval值计算
先看看next数据值的求解方法
例:下标从1开始(若题中给定下标为0开始,把所有值-1即可)
next数组的求解方法:根据前一个字符next,一直循环找到第一次匹配成功的下标,并把next=1;如果当前字符与下标1字符都不相同,next值就为1(初始下标值)
第一位为0,第二位为1,
第三位:把前一个模式串字符b与下标next值所对应的字符比较,b 和a不同,next为1(初始下标值)
第四位:前一个,c c和a不同,next为1
第五位:a和a相同(下标为1)1+1=2
第六位:b和b相同(下标为2)2+1=3
第七位:a和c不同(下标为3),继续找,c下标为1,a和a相同(下标为1) 1+1=2
nextval数组求解方法:根据next数组的值作为下标找到第一个不同的字符,把它的下标作为nextval的值;否则继续循环比较,直到与第一个字符也相同,此时,nextval值为0
第一位为0,第二位为1,
第三位:(当前下标字符)c与a(next值1作为下标的字符进行比较),若不同则为初始下标值1
第四位: a和a相同(第一个字符),nextval值为0
第五位:b和b(下标为2),相同,继续比较,b的next为1,b和下标为1的比,即b和a比,不同,则nextval值为1
第六位:a和c(下标为3),不同,nextval为下标的值 3
第七位:a和b(下标为2),不同,nextval为下标的值 2
注:如果下标从0开始,只需把所有的next和nextval值-1就是
最新文章
- JS框架
- LeetCode ";Design Twitter";
- [转]关于安装hadoop中出现的的 $HADOOP_HOME is deprecated 的解决方法
- 关于nandflash与norflash
- Bzoj 2834: 回家的路 dijkstra,堆优化,分层图,最短路
- Java jdbc数据库连接池总结!(转)
- Shell脚本编程入门(一) 分类: 学习笔记 linux ubuntu 2015-07-09 21:06 29人阅读 评论(0) 收藏
- javascript之url转义escape()、encodeURI()和decodeURI()
- Cocos2d-X中实现菜单特效
- C# 数据库链接字符串加密工具
- 【BZOJ4712】洪水
- RetrieveFavicon 获取任何站点的 favicon
- WebServer Security apache / bind / IIS5
- Go linux 实践 1
- redis集群cluster模式搭建
- docker之数据卷管理
- C# JAVA 记录代码运行时间
- https://developer.mozilla.org/
- SQL server数据库压缩空间
- 服务器部署之nginx的配置
热门文章
- HashSet为什么可以有序输出?
- event loop整理
- 代码安全性和健壮性:如何在if和assert中做选择?
- 后端程序员之路 33、Index搜索引擎实现分析2-对外接口和大体流程
- Linux自学之旅-基础命令(chown和chgrp)
- 使用 Java 开发 Gradle 插件
- 文件查询 select name,age where age>;22
- Hive源码分析(1)——HiveServer2启动过程
- 2020-2021 ACM-ICPC, Asia Seoul Regional Contest
- ch2_8_3求解回文序列问题(递归实现)