腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
3
回答
当KMP的目标是找到某个
字符串
的所有
匹配
项时,最糟糕的情况是什么?
、
、
、
我还想知道在查找一个
字符串
在另一个
字符串
中的所有
匹配
项的所有
算法
中,哪个
算法
的复杂
度
最差。似乎Boyer-Moore
算法
的时间复杂
度
是线性的。
浏览 2
提问于2012-02-08
得票数 11
回答已采纳
1
回答
差分串
匹配
、
使用
字符串
匹配
,您可以查找精确的
匹配
。实际上,该
算法
是另一种
算法
的更一般化的版本,其中另一种
算法
注册的值为1 for effect (a !在最初的
算法
中,如果
字符串
的总不
匹配
浏览 2
提问于2020-07-27
得票数 0
2
回答
二模式
字符串
匹配
算法
、
、
、
、
我需要对时间复杂
度
为O(n+m1+m2)的最长双模式前缀/后缀
匹配
算法
进行编码,其中n是
字符串
的长度,m1是pattern1和pattern2的长度。示例:如果
字符串
为"OBANTAO“,Pattern1为”香蕉“,而Patten2为”午睡“,则答案是
字符串
的子
字符串
"BANTA”,该
字符串
由香蕉的前缀禁令和午睡的后缀TA组成。谷歌的结果是:“Rabin
字符串
搜索
算法
”、“Knuth p
浏览 2
提问于2014-02-17
得票数 5
回答已采纳
3
回答
O(n)子串
算法
、
、
、
、
因此,我对子串搜索
算法
进行了研究,发现大多数
算法
,如kmp
算法
和rabin
算法
,在进行
字符串
匹配
之前都需要额外的时间复杂
度
来进行预处理。这样做有什么好处吗?为什么他们不直接跳到
字符串
匹配
,这样大O时间复杂
度
就不会下降到O(m+n)?我尝试创建一个我认为是O(n)的子
字符串
算法
(如果我错了,请纠正我),只需跳过预处理时间。
浏览 11
提问于2020-01-27
得票数 1
回答已采纳
1
回答
字符串
匹配
和整数
匹配
的时间复杂
度
、
、
、
、
字符串
匹配
和整数
匹配
在时间复杂
度
方面有什么不同? 我要问的是这一点,特别是关于Rabin Karp
算法
。为什么计算每个子
字符串
的哈希码并用给定搜索
字符串
的哈希码检查其相等性比简单地检查子
字符串
是否与给定
字符串
匹配
的简单方法要快呢?
浏览 2
提问于2014-03-10
得票数 2
回答已采纳
1
回答
匹配
多个单词中的
字符串
、
、
我已经找到了许多关于如何在
字符串
中
匹配
多个模式的解决方案,但没有找到如何在许多单词中
匹配
单个
字符串
。到目前为止,我所知道的最好的方法是对每个单词使用KMP
算法
,但这并不是很有效(复杂
度
=单词长度的总和),所以我正在寻找更好的
算法
来做到这一点。
浏览 2
提问于2012-07-19
得票数 0
回答已采纳
2
回答
使用Rabin-Karp搜索
字符串
中的多个模式
、
、
、
、
根据上的拉宾-卡普
字符串
匹配
算法
,它可以用来同时在
字符串
中查找多个不同的模式,同时仍然保持线性复杂
度
。很明显,当所有模式的长度都相同时,这很容易做到,但我仍然不明白当我们同时搜索不同长度的模式时,如何保持O(n)的复杂
度
。有人能解释一下这件事吗?编辑(2011年12月): 维基百科的文章已经更新,不再声称
匹配
O(n)中不同长度的多个模式。
浏览 7
提问于2009-08-23
得票数 17
回答已采纳
2
回答
从一组示例
字符串
中学习(常见的)语法/模式?
、
、
我试图为数据库和
字符串
列制定一个异常值检测
算法
。例如,假设我有以下
字符串
列表:我想要开发一种
算法
来检测
字符串
列表中的常见模式,并指出哪些
字符串
不是这种格式例如,在上面的示例中,我希望这个
算法
检测以下正则表达式:考虑
浏览 0
提问于2020-07-27
得票数 3
回答已采纳
1
回答
如何使用elasticSearch有效
匹配
一个
字符串
中的成千上万个子
字符串
我想在一条信息中
匹配
这些标题,例如: 我试图将所有标题发送到wit.ai,但它似乎无法处理100000个子
字符串
。 我想知道elasticsearch是否能胜任这项工作?
浏览 6
提问于2016-10-26
得票数 0
1
回答
Knuth-Morris-Pratt (KMP)和使用Ukkonen
算法
的后缀树在时间复杂度上的差异。
、
、
、
、
是否有可能找到最长的公共子串,最长的回文子串,最长的重复子串,使用Ukkonen的
算法
同时使用KMP和后缀树搜索所有模式和子串检查?如果是,那么我应该使用哪一个
算法
,因为这两个
算法
都有线性时间复杂
度
?
浏览 19
提问于2016-09-05
得票数 1
1
回答
基于字典的
字符串
匹配
算法
-- Java
、
、
Java中有没有基于字典的
字符串
匹配
算法
? 可以根据字典给出两个
字符串
之间的相似
度
百分比?
浏览 2
提问于2013-01-13
得票数 0
回答已采纳
1
回答
.replace()在within循环中的时间复杂
度
(Big-O)是多少?
、
、
、
、
我正在与我的同行讨论一个关于如何计算
字符串
中未配对括号的
算法
问题的最佳方法。以下是问题描述的摘录: 如果
字符串
中的每个开口括号都可以与后面的结束括号配对,则认为括号
字符串
是正确
匹配
的,反之亦然。例如,“(())()”是正确
匹配
的,而“)(”和“(”不是“)(例如,”(“)”可以通过在末尾添加两个尾括号来正确
匹配
,因此您将返回2。考虑到这一点,我提出了一个无可争辩的O(1)空间解,但他声称,由于.replace()方法是线性的,同时循环也是线性的,因此它也是N^2时间复杂
浏览 2
提问于2022-08-31
得票数 0
回答已采纳
1
回答
Boyer-Moore
字符串
搜索
算法
运行时复杂
度
、
、
、
那么,Boyer
算法
的正确运行时复杂
度
是多少?
浏览 2
提问于2015-10-06
得票数 1
1
回答
用WordNet路径
算法
计算两个
字符串
中词的语义相似
度
、
、
、
我在其他集合中也有多个
字符串
,比如s2、s3、s4。 我想将
字符串
s1中的单词与每个
字符串
s2、s3等进行
匹配
。根据最大相似
度
评分,我希望从s2、s3中找出哪些
字符串
与s1最大
匹配
。我想使用wordNet的路径
算法
。请建议,什么应该是最好的方法。
浏览 8
提问于2015-07-05
得票数 1
6
回答
百分比相似
度
分析(Java)
、
我有以下情况:有没有什么想法或标准
算法
来计算相似
度
百分比?例如,在上面的情况下,通过人工查找估计的相似
度
应该是90%++。有谁能给点指导吗?因此,
匹配<
浏览 2
提问于2010-03-06
得票数 4
回答已采纳
1
回答
字符串
模式
匹配
的KMP
算法
和Z
算法
有什么不同?
、
、
在KMP
算法
中,我们对模式进行预处理,找出最长的前缀,以便在
匹配
时跳过字符。而在Z
算法
中,我们首先生成一个新的
字符串
其中x=在模式和
字符串
中都不存在的字符两者的时间复杂
度
均为O(m+n)。那么,这两种
算法
之间的区别是什么,哪一种最适合使用?
浏览 5
提问于2021-04-28
得票数 0
2
回答
Z
算法
背后的直觉
Z
算法
是一种具有O(n)复杂
度
的
字符串
匹配
算法
。 一个用例是从
字符串
B中找到最长的
字符串
A。例如,来自"overdose"的"stackoverflow"出现时间最长的是"over"。您可以通过使用组合
字符串
"overdose#stackoverflow"调用Z
算法
(其中#是两个
字符串
中不存在的某个字符)来发现这一点。然后,Z
算法
浏览 0
提问于2016-01-10
得票数 3
1
回答
最长公共子串
算法
O(n*m)暴力破解
、
我在看上的
算法
它们使用动态编程,这为它们提供了O(nm)的时间。然而,用蛮力
算法
不能达到同样的时间复杂
度
吗?我正在做一个作业题,在O(n*m)时间内找到这个
算法
,其中n和m是
字符串
长度。对于
字符串
A和
字符串
B,我检查Ai是否等于B中的任何元素。如果它等于某个Bj,则检查Ai +1是否等于Bj + 1,如果Ai +2= Bi +2,依此类推,直到不再
匹配
或
字符串
结束。如果是不
匹配
的情况,那么从我们在B中检查的最后一个
浏览 0
提问于2012-10-15
得票数 1
回答已采纳
1
回答
Python
字符串
“in”运算符实现
算法
和时间复杂
度
、
、
、
例如,我正在考虑in操作符如何实现>>> s2 = 'bcd'True 在CPython中,使用哪种
算法
来实现
字符串
匹配
,时间复杂
度
是多少
浏览 0
提问于2013-08-09
得票数 35
回答已采纳
1
回答
如果模式
字符串
中的所有字符都是唯一的/不同的,那么KMP如何接受O(m+n)
、
例如:所以看起来,模式的
匹配
总是从第0索引开始。在源
字符串
中,
字符串
将逐字符移动。 因此,它似乎应该具有O(m_n)的复杂性。一般说来,我可以说KMP应该有O(m_n)的最坏情况复杂
度
,但是我读到用KMP可以解决O(m+n)中的相减
匹配
算法
,所以我很想知道最坏的情况分析。
浏览 2
提问于2017-07-04
得票数 3
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
算法字符串匹配-BF算法
算法 KMP字符串匹配
字符串匹配算法基础版
漫画:什么是字符串匹配算法?
通俗理解 KMP 字符串匹配算法
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券