qq_43412960 2020-05-06 09:48 采纳率: 76.5%
浏览 149
已采纳

这是一个关于数据结构kmp算法的相关问题

kmp算法，可以加快找字串位置的速度。
为什么加快呢，因为在每次比较过程中，找到了模式串对称的小串，然后直接移过去。
比如，主串abcabcabe,模式串abcabe。
第一次，匹配到主串的第二个c，失败，然后根据前面串的对称串ab，
第二次首先匹配第二个ab的首位置。
我的疑问是，跳过中间的字符匹配，会不会造成误差呢？比如少了些匹配成功的机会

  • 写回答

2条回答 默认 最新

  • threenewbee 2020-05-06 10:03
    关注

    不会。跳过去的是前缀肯定不符合的，它肯定不能构成模式串

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

  • 这是一个关于数据结构的kmp算法问题 c++
    2020-05-05 11:12
    回答 1 已采纳 https://blog.csdn.net/shiwanghualuo/article/details/52432137
  • 数据结构KMP的时间复杂度 开发语言 数据结构 算法
    2023-04-19 21:40
    回答 2 已采纳 m+n和n其实都是O(n)
  • kmp算法|请问一下这句是什么意思啊 数据结构 算法
    2021-10-06 14:47
    回答 1 已采纳 这个就涉及到了next数组了。kmp相对朴素匹配的优势就是next数组。当我们子串ababa已经匹配上的情况下，第六个不匹配了，我们总不能回到刚开始的主串的下一个，子串的第一个重新开始，我们可以看见a
  • 数据结构KMP算法配图详解（超详细）
    2020-02-18 22:02
    哈顿之光的博客 KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练，但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...
  • 这是一个关于数据结构字符集问题 c++
    2020-05-06 13:08
    回答 1 已采纳 这里的移动，是指用一个指针或者代表下标的整数去扫描这个字符串。这个指针++，就相当于向右移动。
  • 想问下数据结构与算法该怎么看书自学 数据结构 算法 职场和发展
    2021-10-31 15:49
    回答 2 已采纳 第一遍建议先看书，尽量去记代码，然后自己敲，哪里不会就去看书，多练习就好了
  • KMP算法求next数组 c语言 数据结构 算法
    2022-03-25 21:03
    回答 1 已采纳 书中T[0]存储的是字符串长度，而你代码中T[0]是包含字符的，所以你代码next计算的时候没有计算到第一个字符。
  • 数据结构KMP算法配图详解
    2024-01-15 18:10
    在这个"数据结构KMP算法配图详解"中，我们将深入探讨该算法的原理、实现以及它在C语言和Java中的具体应用。 1. KMP算法概述： KMP算法由D.E. Knuth、V.R. Morris和J.H. Pratt于1970年提出，它的核心思想是避免对已...
  • kmp算法无法正常运行 数据结构
    2022-11-23 10:50
    回答 1 已采纳 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7490905我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：KMP
  • 数据结构字符串匹配问题，急！！ c++ 数据结构 算法
    2017-04-20 10:56
    回答 3 已采纳 ``` #include #include using namespace std; int *COMPUTE_PREFIX_FUNCTION(string P) { i
  • 自己写的KMP算法，出了点问题 c++ 算法
    2021-08-15 12:56
    回答 1 已采纳 C++中string类size() 函数的返回值是无符号数,所以判断的地方需强制类型转换下,供参考： #include<iostream> #include<string> u
  • 严蔚敏 数据结构 kmp算法详解.pdf
    2024-04-12 23:29
    与暴力搜索算法不同，KMP算法通过一个称为失配表（failure function）或部分匹配表（Partial Match Table）的预处理数据结构，来避免从文本串中每次不匹配后都重新从模式串的头开始匹配，从而大大提高了匹配效率。...
  • 改进KMP算法.zip_KMP算法_c语言数据结构
    2022-07-15 21:35
    标题中的“改进KMP算法.zip_KMP算法_c语言数据结构”指的是一个关于KMP（Knuth-Morris-Pratt）算法的项目，该算法在C语言的数据结构背景下进行了优化。KMP算法是一种高效的字符串匹配算法，它避免了在发现不匹配字符...
  • 数据结构之KMP算法
    2020-03-08 12:18
    数据结构是计算机科学中的核心概念，它涉及到如何高效地存储和...学习KMP算法有助于提升解决相关问题的能力，如文本分析、文件查找等。通过深入研究压缩包中的代码和文档，可以进一步提升对KMP算法的理解和应用技巧。
  • java数据结构与算法.pdf
    2022-01-04 17:39
    Java作为广泛应用的编程语言，其在实现数据结构和算法时有着丰富的库支持和优秀的可读性。下面将对标题和描述中提到的一些关键知识点进行详细解释。 1. **数据结构**： - **稀疏数组**：当大量数据中大部分为零或...
  • 数据结构KMP算法 C
    2016-07-05 15:41
    在众多数据结构中，字符串处理是一个重要领域，而KMP（Knuth-Morris-Pratt）算法则是用于字符串匹配的高效算法。KMP算法是由D.E. Knuth、V. Morris和J.H. Pratt在1970年代共同提出的，主要用于解决在一个长字符串...
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 安装opengauss数据库报错
  • ¥15 【急】在线问答CNC雕刻机的电子电路与编程
  • ¥60 在mc68335芯片上移植ucos ii 的成功工程文件
  • ¥15 笔记本外接显示器正常，但是笔记本屏幕黑屏
  • ¥15 Python pandas
  • ¥15 蓝牙硬件，可以用哪几种方法控制手机点击和滑动
  • ¥15 生物医学数据分析。基础课程就v经常唱课程舅成牛逼
  • ¥15 云环境云开发云函数对接微信商户中的分账功能
  • ¥15 空间转录组CRAD遇到问题
  • ¥20 materialstudio计算氢键脚本问题