当前位置: 首页 > news >正文

旅游网站建设水平评价福州商城网站建设

旅游网站建设水平评价,福州商城网站建设,wordpress后台登陆太慢,网站如何做信息表前言 本文结合朱战立教授编著的《数据结构—使用c语言#xff08;第五版#xff09;》#xff08;以下简称为《数据结构#xff08;第五版#xff09;朱站立》#xff09;中4.4.2章节内容编写#xff0c;KMP的相关概念可参考此书4.4.2章节内容。原文中代码是C语言…前言 本文结合朱战立教授编著的《数据结构—使用c语言第五版》以下简称为《数据结构第五版朱站立》中4.4.2章节内容编写KMP的相关概念可参考此书4.4.2章节内容。原文中代码是C语言本文改用Go语言编写逻辑不变。 一、KMP介绍 ‌KMP算法‌Knuth-Morris-Pratt算法是一种高效的字符串匹配算法由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心在于利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的时间复杂度为O(mn)其中m和n分别代表模式串和主串的长度。 二、求next数组 next数组是KMP算法中核心概念求出next数组后在模式串元素和主串元素比较的失败的时候可以将模式串t直接偏移到以next数组中的元素为下标的位置主串指针不偏移减少了元素比较次数下面我们直接求next数组 举例 字符串s“ababbababcabac” 模式串t“ababcab” go语言版求next数组的代码如下 func GetNext(s string) []int {var next []int make([]int, len(s))next[0] -1next[1] 0// j表示当前要求next值的位置// k表示当前要和前一个字符比对的下标j, k : 1, 0for j len(s)-1 {if s[j] s[k] {next[j1] k 1kj} else if k 0 {next[j1] 0j} else {k next[k]}}return next }执行上面代码我们能获取到next数组如下 PS D:\Project\GoWorkSpace\DataStructure go run .\0113\KMP_Algorithm.go [-1 0 0 1 2 0 1]注以上代码的变量名称逻辑均与《数据结构第五版朱站立》中内容一致方便代码阅读 三、图解KMP匹配过程 中间部分循环过程省略主要看当模式串和主串不相等时模式串如何偏移 字符串s“ababbababcabac” 模式串t“ababcab” next数组[-1 0 0 1 2 0 1] 第一步s数组元素和t数组元素一一对比如果成功两个数组下标偏移同时1继续比较以此类推 第二步当s[4]≠t[4]时next[4]2s数组不偏移t数组偏移到t[2]比较s[4]和t[2] 第三步当s[4]≠t[2]时,next[2]0,s数组不偏移t数组偏移到t[0]比较s[4]和t[0] 第四步当s[4]≠t[0]时由于t数组已经到第一位所以s数组下标1比较s[5]和t[0] 第五步当s[5]t[0]时回到了第一步两个数组下标偏移同时1继续比较以此类推当t的下标为7时s的下标为12循环结束打印t的第一个元素在s中下标的位置即12-75 四、Go示例代码 package mainimport fmtfunc KMP(s string, t string) int {m : len(s)n : len(t)// s中当前比对的位置是i// t中当前比对的位置是ji, j : 0, 0next : GetNext(t)for i m j n {if s[i] t[j] {ij} else if j 0 {i} else {j next[j] // t串偏移偏移到next[j]下标}}if j n { // t串全部匹配return i - j} else {return -1} } func GetNext(s string) []int {var next []int make([]int, len(s))next[0] -1next[1] 0// j表示当前要求next值的位置// k表示当前要和前一个字符比对的下标j, k : 1, 0for j len(s)-1 {if s[j] s[k] {next[j1] k 1kj} else if k 0 {next[j1] 0j} else {k next[k]}}return next } func main() {t : ababcabfmt.Println(GetNext(t))fmt.Println(KMP(ababbababcabac, t)) }运行结果 PS D:\Project\GoWorkSpace\DataStructure go run .\0113\KMP_Algorithm.go [-1 0 0 1 2 0 1] 5
http://www.w-s-a.com/news/475628/

相关文章:

  • site之后网站在首页说明说明网络舆情分析师怎么考
  • 本溪网站建设兼职wordpress lapa
  • 官网网站设计费用vue大型网站怎么做路由
  • 青海省安建设管理部门网站厦门网站快照优化公司
  • 张家港建网站公司网站开发 认证
  • 网站建设方式优化兰州医院网站制作
  • 怎么创造网站wordpress伪静态规则怎么写
  • 自己怎么做一元购物网站信誉好的合肥网站推广
  • 做网站的骗术有什么好的网站设计思想的博客
  • 网站建设工作 方案企查查企业信息查询在线
  • 上海外贸建站商城定制软件安卓
  • 成都网站建设_创新互联wordpress 相邻文章
  • 电子商务网站制作步骤免费建网站知乎
  • 龙岩有什么招聘本地网站团购网站 方案
  • 服务器运行一段时间网站打不开注册公司名字核名查询系统
  • 企业网站改版的意义响应式网站建设新闻
  • 大连金州新区规划建设局网站金坛市建设局网站
  • 有哪些做排球比赛视频网站wordpress 教师工作坊
  • 深圳好点的网站建设公司互联网企业信息服务平台
  • 下载空间大的网站建设哈尔滨网站制作软件
  • 南城网站仿做无锡网站制作哪家价格便宜
  • c做的网站营销策划课程
  • 免费网站404免费进入重庆的公需科目在哪个网站做
  • 网站空间租用费用网站建设公司怎么宣传
  • 镇江网站建设优化案例分析dw2018网页制作步骤图文
  • 网站开发一个多少钱为什么前端都不用dw
  • 网站降权的原因北京中小企业网站建设公司
  • 个人域名能做网站吗wordpress
  • 手机网站设计只找亿企邦工业设计公司简介
  • 腾讯云主机做网站免费网站怎么做啊