程序员经验分享-hwhale

KMP 字符串搜索算法的最坏情况是什么？ [关闭]

2024-03-13

谁能建议我一个最坏情况的“文本字符串 - 模式对”来测试 KMP 算法实现？


我会说像这样的模式

xx........x
| n times |

和一个像这样的字符串

xxx.........xyx...........xy....
| n-1 times | | n-1 times |

将是最糟糕的情况之一，但它仍然O(m+n)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Testing

complexitytheory

KMP 字符串搜索算法的最坏情况是什么？ [关闭] 的相关文章

  • 如何在给定目标索引数组的情况下对数组进行就地排序？

    你如何对给定的数组进行排序arr in place给定目标索引数组ind 例如 var arr A B C D E F var ind 4 0 5 2 1 3 rearrange arr ind console log arr gt B E

  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d

  • 快速求解子集和

    考虑这种解决子集和问题的方法 def subset summing to zero activities subsets 0 for activity cost in activities iteritems old subsets sub

  • EDI AS2 HTTP 跟踪？

    我们正在研究 AS2 实现 并希望能够构建有意义的测试用例以与 SoapUI 或 Postman 一起使用 为了做到这一点 我们有两种方法 只是尝试从现有客户端进行 tcp 转储 跟踪调用 从普通 EDI 文档开始手动构建一些简单的调用 或

  • 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的差异

    我最近偶然发现了一个资源 其中 2T n 2 n log ntypeMM 宣布复发无法解决 我接受它作为一个引理 直到今天 另一种资源被证明是矛盾的 在某种意义上 根据资源 下面的链接 其中的 Q7 和 Q18 是建议 分别在问题中的1和2

  • 检索受“rowspan”影响的行的列索引的最有效方法是什么？

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb

  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要

  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he

  • 固定大小集以包含给定集的最大数量

    我有大约 1000 组尺寸 1 4 1 3 3 5 6 4 5 6 7 5 25 42 67 100 是否有可能找到包含最大数量的给定集合的大小为 20 的集合 检查每一个100 80 20 集 效率低下 我不太确定这是 NP 完全的 考虑

  • 解释一下从 N 个给定集合中的每一个中给出第 K 个最大数字的示例？

    今天我尝试解决一个Facebook 编程挑战赛 https facebook interviewstreet com recruit challenges 我遇到的挑战是 酒吧问题 可以找到here https github com alo

  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有

  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1

  • 7 张牌扑克手牌评估器

    有谁知道评估 7 张牌扑克牌的快速算法吗 这比简单地暴力检查 7 张牌中每 21 个 5 张牌的组合更有效 Cheers Pete 我写了一篇JavaScript 核心评估方法仅使用位操作 因此速度非常快 考虑到这一点 查看 21 种组合还

  • 带路径压缩算法的加权 Quick-Union

    有一种 带路径压缩的加权快速联合 算法 代码 public class WeightedQU private int id private int iz public WeightedQU int N id new int N iz new

  • 如何发送wei/eth到合约地址？ （使用truffle javascript测试）

    我正在尝试将 wei eth 发送到我的 Solidity 合约的地址 该合约具有外部应付回退功能 我下面的 truffle javascript 测试不会导致 instance address 的余额获得任何 wei instance a

  • 我可以将参数作为数组传递吗？

    例如 而不是 assert eq add 2 3 5 有什么方法可以调用类似的东西 let params u32 2 2 3 assert eq call add params 5 我发现这个功能对于测试非常有用 例如 如果我想为需要大量参

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 使用 VCR 过滤敏感数据

    我正在使用 VCR gem 记录 http 交互并在将来重播它们 我想过滤掉 uri 请求中的实际密码值 以下是 uri 的示例 http services somesite com Services asmx Cabins Usernam

  • 如何在 Django Rest 框架中编写“删除”操作的测试

    我正在为 Django Rest Framework API 编写测试 我一直在测试 删除 我对 创建 的测试工作正常 这是我的测试代码 import json from django urls import reverse from re

  • 如何测试某些代码在 C++ 中无法编译？ [复制]

    这个问题在这里已经有答案了 可能的重复 单元测试编译时错误 https stackoverflow com questions 605915 unit test compile time error 我想知道是否可以编写一种单元测试来验证给

随机推荐

  • 如何在弹出菜单中使用单选按钮？

    我正在尝试创建一个包含可选单选按钮的弹出菜单 以便更改视图类型 例如图库 卡片 滑动 网格 列表等 我遇到的问题是 PopupMenu 有自己的用于选择值的回调 Radio 和 RadioListTile 也是如此 忽略RadioListT

  • 自动将调试器附加到 Eclipse 中的新 Java 子进程

    我有一个 Java 进程 它使用 ProcessBuilder 等生成一个新的 JVM 在调试时 是否可以让 Eclipse 将调试器附加到新的子进程 更好的是 是否有任何插件在注意到新的子进程时会自动执行此操作 我被告知 虽然还没见过 V

  • 哈希表真的可以是 O(1) 吗？

    哈希表可以实现 O 1 似乎是常识 但这对我来说从来没有意义 有人可以解释一下吗 我想到了以下两种情况 A 该值是一个小于哈希表大小的 int 因此 该值是它自己的哈希值 因此不存在哈希表 但即使有 也会是 O 1 并且效率仍然很低 B 您

  • 在 Podfile 中声明架构

    有没有办法将架构包含在 CocoaPods 中Podfile 我正在尝试为 32 位和 64 位构建我的应用程序 但是当我切换到Standard architectures including 64 bit 在我的项目的构建设置中 它抱怨我

  • css：覆盖活动链接样式？

    我的 css 中有以下选择器 a active position relative top 1px 因此 每个链接在按下时都会有这个小按钮效果 我怎样才能防止特定链接的这种行为 例如我的网站上有一个 返回顶部 链接 不应该有这种行为 a b

  • 标准 Treeview 的 C# 替代品？

    我想找到提供的 System Windows Form Treeview 的替代品 我需要以下改进 多项选择项目 更好的性能 标准小部件的性能简直太糟糕了 特别是在添加一长串项目时 在树视图小部件内拖放项目时滚动 我可能会忘记一些 但这些非

  • s3 安装在容器内。如何将其暴露给主机？

    我一直在考虑是否有一个容器可以安装 s3 桶并将其暴露在外面 I used https github com FindHotel aws s3 mount https github com FindHotel aws s3 mount将 s

  • 拖放文本视图

    我必须拖动 但无法完美拖动它 问题是 1 我必须拖动两到三次才能将其带到所需的位置 因此 textview 不能顺利跟随手指移动 2 如果我向上移动文本视图 它只会向下移动 我提供了触摸事件上textview的代码 请帮忙 提前致谢 fin

  • 如何使用 Unix 套接字对来通信 Rust 和 Ruby 进程

    我正在尝试使用 Unix 套接字对将 Rust 进程与 Ruby 子进程进行通信 我只使用 Ruby 尝试过同样的操作 它可以工作 但我似乎无法让它与 Rust 一起工作 我尝试将 rust socket 文件描述符传递给Ruby脚本 将

  • python 中的聚合时间序列

    我们如何按小时或分钟粒度聚合时间序列 如果我有如下所示的时间序列 那么我希望这些值按小时聚合 pandas 是否支持它 或者是否有一种在 python 中实现它的好方法 timestamp value 2012 04 30T22 25 31

  • 应用内购买产品 ID 是否必须以反向 DNS 开头？

    应用内购买产品 ID 是否必须以反向 DNS 开头 例如com mycompany My Awesome Game Level Pack 1或者它可以只是独立的吗Level Pack 1 产品 ID 可以是您想要的任何内容 但建议您遵循反向

  • 使用 rma.glmm 计算估计值：当 2 个估计值相同时出错

    我正在使用 rma glmm 来计算两项不同研究的元比例 例如 6 个月时出现 xi 和未出现 xii 不良事件的个体比例 library metafor 6 months study c 1 2 ni c 41 19 xi c 26 14

  • 浏览器后退按钮未更新页面

    我使用 jquery 单击事件在井号标记后设置 URL URL 设置正确 但当我使用浏览器后退按钮时 它不会将我带到上一页 在我的点击事件之前 URL 如下所示 http example com menu php home 我的点击事件如下

  • 如何使用 JavaZOOM JLayer 库播放/暂停 mp3 文件？

    如何向以下代码添加播放 暂停按钮 import javazoom jl player Player try FileInputStream fis new FileInputStream mysong mp3 Player playMP3

  • 更新至 Safari 12.0 - Java 插件不再列出

    更新到后Safari 版本 12 0 下面的Java插件Safari gt 首选项 gt 网站 gt 插件不再列出 因此 Java Applet 不能在不安全模式下运行 有没有办法启用 Java 插件或运行 Java 小程序 在 macOS

  • Pandas：条件组特定计算

    假设我有一个带有键 例如客户 ID 和两个数字列 C1 和 C2 的表 我想按键 客户 对行进行分组 并在其列上运行一些聚合器 例如 sum 和 Mean 在计算组聚合器之后 我想将结果分配回 DataFrame 中的每个客户行 因为一些客

  • ReactJS HREF 导致状态丢失

    我有一个名为 EnrollForm 的父组件 带有一个 BrowserRouter 该组件路由到不同的子组件 这些子组件是我的整个 EnrollForm 的页面 每次填写子组件页面并单击下一个 btn 时 所有表单字段都会保存到子组件状态

  • 多项式评估的生成方法

    我试图想出一种优雅的方法来处理一些生成的多项式 对于这个问题 我们将 专门 关注以下情况 order是生成的参数n三阶多项式 其中 n order 1 i是 0 n 范围内的整数参数 多项式在 x j 处有零点 其中 j 1 n 且 j i

  • 在 Perl 6 中查找上周五的日期？

    我想生成一个从周一到周四的上周五结束的序列 如果该序列从周六和周日开始 则生成上周五结束的序列 也就是说 假设今天是2018 05 09 那么上周五是2018 05 04 如果今天是2018 05 12 那么上周五是also 2018 05

  • KMP 字符串搜索算法的最坏情况是什么？ [关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 谁能建议我一个最坏情况的 文本字符串

热门标签