5回答
假设我有以下内容：
Lorem Ipsum is simply dummy text of the printing and typesetting industry.
如何使用C在字符串中搜索dummy或dummy text？是否有任何简单的方法来做这件事，或者只对强字符串操作？我所需要的只是搜索它，并返回一个布尔值和结果。
编辑：
你们围绕这个话题进行了一次大讨论，并提出了一些算法，我不介意，因为这可能对其他人有用，甚至对将来的我也有用。但我真正想要的是最简单的方法，不管时间和空间的复杂性。这对我做什么并不重要。因此，strstr轻松而迅速地解决了我的问题。我真的得给我买一些标准的C函数切
浏览 16提问于2010-03-27得票数 2
回答已采纳
有人能帮我理解一下哪一个是更有效的strstr()还是KMP，因为最近我在SPOJ上做了一个问题，发现strstr()在某种程度上比KMP快。请有人解释一下背后的奥秘。
浏览 4提问于2013-12-12得票数 2
回答已采纳
1回答
我正在读一本书“数据结构的理论与问题”(Seymour Lipschuz)。
让我提供我正在阅读的部分的图像。
。
本书的这一部分讨论了一种名为“第二模式匹配算法”的模式匹配算法。
这是什么算法？这是Boyer-Moore还是KMP或者Horspool还是什么？
或者，这是作者提出的新算法吗？
浏览 0提问于2011-07-09得票数 4
回答已采纳
我读了java.lang.String的源代码，我惊讶地发现String.indexof()不使用？如我们所知，KMP更有效。那么为什么String.indexOf()不使用它呢？
我周围的人告诉我，对于短字符串，KMP已经足够好了，但是如果您需要性能，并且打算使用大字符串，那么就不是一个好的选择。但是他没有告诉我细节。
下面是我的问题：
我们为什么不在String.indexOf()中使用KMP呢？
为什么KMP不是一个大字符串的好选择？
浏览 6提问于2013-10-23得票数 30
回答已采纳
我遇到了用于子字符串搜索的KMP算法，并在python中实现了它。后来，我发现in运算符也可以用来解决这个问题，我决定比较它们的性能。令我惊讶的是，in比KMP算法快得多，我决定仔细看看in。 我发现in在一个字符串中实现了__contains__方法，该字符串用于Datamodel doc中建议的包含检查。但不能进一步解释为什么它更快。 下面是我的KMP算法的实现： def lps(pattern):
start_ind = 0
lps_list = [0]
for j in pattern[1:]:
if(j == pattern[start_in
浏览 18提问于2019-04-06得票数 7
回答已采纳
1回答
我正在尝试对一组由正则表达式匹配的子域执行路由规则。
iptables -t nat -A PREROUTING -m string --string "/must-[a-z0-9-\.]+gonow[a-z\.]+/g" --algo regex -p tcp -m tcp --dport 12 -j DNAT --to-destination 1.1.1.1:12
获取错误- iptables:没有链表/目标/匹配的名称。
浏览 0提问于2018-01-31得票数 1
回答已采纳
是否有可能找到最长的公共子串，最长的回文子串，最长的重复子串，使用Ukkonen的算法同时使用KMP和后缀树搜索所有模式和子串检查？如果是，那么我应该使用哪一个算法，因为这两个算法都有线性时间复杂度？
浏览 19提问于2016-09-05得票数 1
1回答
什么时候适合使用KMP算法？
、、、、
我理解KMP算法依赖于助手数组，即有类似于后缀的前缀。当不满足上述条件时，它将不会有效率，因为在helper数组中包含的都是零。运行时间会是O(m + n)吗？如果我是对的，在这种情况下，什么是更好的子串算法？
浏览 8提问于2017-02-23得票数 1
回答已采纳
1回答
查看KMP算法，并对KMP中计算后缀-前缀计数表的特定行感到困惑。
算法kmp_table:输入:字符数组，W(要分析的单词)整数数组，T(要填充的表)输出:无(但在操作期间，它会填充表)
define variables:
an integer, pos ← 2 (the current position we are computing in T)
an integer, cnd ← 0 (the zero-based index in W of the next
character of the current candidate substring)
(th
浏览 0提问于2013-03-21得票数 1
1回答
我正试图解决这个问题，我无法到达线性时间。
如果字符串T可以以T=PPP..P的形式表示，则称为周期性。
设计一种确定给定T是否为周期的线性时间算法，若为真，则求出最短周期。
我的方法是:如果T=AB=BA那么T是periodical，我的算法会一直检查字符串是否可以这样表示，如果是，我会检查其中的一半。
这需要O(n*log(n)) time。
谢谢各位
浏览 0提问于2018-01-25得票数 0
回答已采纳
1回答
我试图使用Aho-Corasick和单维KMP的组合来解决二维搜索问题，但是，我仍然需要更快的东西。
为了详细说明，我有一个大小为n1*n2的字符矩阵A，我希望找到大小为m1*m2的较小矩阵B的所有匹配项，如果可能，我希望它的大小为O(n1*n2+m1*m2)。
例如：
A = a b c b c b
b c a c a c
d a b a b a
q a s d q a
和
B = b c b
c a c
a b a
该算法应该返回匹配的左上角的索引，在这种情况下应该返回(0,1)和(0,3)。请注意，这些引用可能会重叠。
浏览 2提问于2012-02-16得票数 5
我有字符串"hrhrhrhrhr“。
我想找出t的最小子串，这样我们就可以通过多次将该子串添加到其本身中来生成整个字符串。
在这个例子中，我可以通过四次在"hr“后面加上”hr“来使字符串"hrhrhrhrhr”。
如何找到这种子串？例如，"abc“然后”abc“就是答案。
"ttttttt“-> "t”是应答。
“->”就是答案。
我应该使用哪种算法或具体的方法？
浏览 1提问于2017-01-06得票数 0
我目前正在学习模式匹配算法，并遇到了这两种算法。我有以下大体的想法：
KMP
将文本与失败数组进行比较以移位字符串O(m)，其中m是模式的长度，以计算失败数组花费O(m)，花费O(n)，time to intelligentlytakes a
黑石
比较上一个代码中的模式坏字符跳转和好后缀跳转需要O(m +字母表大小)来计算表需要O(m +字母表大小)，空格需要O(n)，但通常更好的搜索<代码>F223</代码>
我遇到了下面的问题，它触发了这个问题(对或错)：
如果我们想要在许多不同的文本中重复搜索相同的模式，算法是一个很好的选择。
所以我相信答案是正确的，因为假设
浏览 58提问于2013-04-18得票数 27
2回答
Rabin搜索算法工作得很好，但是谁能帮助我将其修改为递归搜索呢？。例如：
* **pattern:** rar
* **text:** abacadabrararbracabrarararacadabrabrarbracad
* **match1:** rar
* **match2:** rar
* **match3:** rar
* **match4:** rar
* **match5:**
浏览 2提问于2012-01-17得票数 1
回答已采纳
1回答
模式识别1d数据
、、
我想在一些光谱中找到模式。
图案应该看起来像2在灰色的圆圈在图片上，所有的数据看起来相似。浅蓝色线条是原始数据，深蓝色虚线-平均值超过6个点。我试着做一些大小的窗口和扫描数据，并检查y-通量值是否下降/上升到60ish%以下，但似乎找到了其他区域和我想要的区域，或者只有这个我不想要。
在光谱中，图案的宽度并不总是相同的。有一张带有黑色虚线图案的光谱图片，但我的程序没有找到它。
我试着改变窗口的大小，但没有用。我可以使用某种模式识别算法来找到这些模式吗？谁能给我指个方向？或者用一种简单的方式解释，因为我有点迷失在这里面了，好吗？
这是我的代码：
import numpy as np
impor
浏览 1提问于2017-03-26得票数 1
我注意到，当KMP算法在Haystacka和Needleb上发现不匹配时，它只是咨询失败函数，但它从不查看Needleb是什么。如果我们考虑Needleb是什么，有可能使KMP更快吗？
浏览 19提问于2020-04-17得票数 0
1回答
我已经看到了这个算法的几个实现，例如具有2个计数器和前缀迭代的实现，或者使用递归的实现。然而，我很难理解使用动态编程的方法。
由于我的知识肤浅，这是我设法想出的：
def sufperf(S):
Pi = [0 for i in range(len(S))]
for i in range(1, len(S)):
p = Pi[i - 1]
while p > 0 and S[i] != S[p]:
p = Pi[p-1]
if S[i] == S[p]:
p += 1
浏览 25提问于2019-08-15得票数 0
1回答
如果我的模式是"Brudasca"，那么KMP前缀表将全部清零。在这种情况下，KMP和普通解决方案之间是否存在性能差异？这不是O(n*m)的最坏情况吗？
浏览 15提问于2017-07-24得票数 1
回答已采纳
2回答
求kmp算法预处理部分的时间复杂度
我在学习关于KMP的知识。但是我不能理解这个algorithm.Can的时间复杂度，有人能解释一下吗？
浏览 2提问于2019-07-16得票数 0
除了Knuth-Morris-Pratt，Rabin-Karp和likes of it之外，还有什么可用的字符串匹配算法？
浏览 5提问于2011-02-24得票数 3
1回答
我希望在一个字符串中搜索另一个较短的字符串，该字符串可能包含与零个或多个字符匹配的通配符*。例如，如果主字符串是“正在搜索此字符串中的子字符串”，并且搜索字符串是" is *ing“，则应该在"is string”处返回匹配。用于这种搜索的算法是什么？现有的大多数算法都执行全局匹配或模式匹配，但它们不执行子字符串搜索。
浏览 4提问于2014-08-20得票数 2
1回答
我已经找到了许多关于如何在字符串中匹配多个模式的解决方案，但没有找到如何在许多单词中匹配单个字符串。
到目前为止，我所知道的最好的方法是对每个单词使用KMP算法，但这并不是很有效(复杂度=单词长度的总和)，所以我正在寻找更好的算法来做到这一点。
浏览 2提问于2012-07-19得票数 0
回答已采纳
3回答
我正在测试这个网站上的字符串搜索算法：。测试文本是1个GByte大小的DNA碱基的随机序列。测试模式是随机大小(最大1kb)的随机序列的列表。测试系统为AMD Phenom II Windows955，GHz为3.2，内存为4 GB，Windows7为64位。代码用C编写，并使用带有-O3标志的MinGW编译。
朴素搜索算法对于短模式需要4秒，对于1kB模式需要8秒。确定性有限状态机对于短模式需要2秒，对于1kB模式需要4秒。Boyer-Moore算法对于非常短的模式需要4秒，对于短模式大约需要1/2秒，对于1kB的模式大约需要2秒。其余算法的性能比朴素搜索算法差。
如何才能使朴素搜索算法搜索
浏览 2提问于2013-11-16得票数 3
我知道KMP (Knuth-Morris-Pratt)和BM (Boyers Moore)算法都是很好的字符串搜索操作算法。我也知道BM比KMP快3-5倍。
根据您从事工业软件编程的经验，您是否使用过BM或KMP算法？算法在这里真的很重要吗？
浏览 3提问于2011-04-09得票数 4
回答已采纳
1回答
KMP DFA前缀函数
、、、
我被要求学习KMP DFA，我在我的书中找到的是实现，但我们的讲师一直将某些东西称为“前缀函数”。我真的不能理解这个函数的哪一部分，有人能给我解释一下吗？如果有人问我这个问题，我很抱歉，但我找不到。
public class KMP {
private String pat;
private String t;
private int[][] fsm;
public static final int ALPHABET = 256;
public KMP(String pat) {
this.pat = pat;
char[] pattern = pat.toCharArra
浏览 5提问于2013-11-24得票数 0
1回答
例如，我有句话：
This is a trash bag.
，它存储在一个列表中，其中每个元素都是一个单词：
List<String> wrodList = new ArrayList<String>;
我有另一本字典，用来存储单词-freq对：
Map<String, Integer> allWords = new HashMap<String, Integer>();
有几个例子：
bag 300
trash 250
trash bag 100
big trash bag 50
现在我想通过wordList
["thi
浏览 2提问于2017-05-23得票数 1
1回答
我想开发一个音乐系统应用程序的模式搜索算法，它搜索给定的关键字并播放其文本文件包含给定关键字的音乐。目前有许多模式搜索算法能够有效地完成这一任务(例如: KMP、散列(可能出错)等)。但我的主要问题是，整个数据库是以英语以外的语言(具体而言，是“印地语”)。现在，用户以“印地语”输入给定的关键字，我希望在数据库中搜索，其中也包含“印地语”语言。我主要关心的是如何有效地在这个数据库中进行搜索？
我认为我们不能为非英语语言做KMP算法，因为我们使用的ascii字符只包含英文字母和其他数字字母，但不包含其他语言的字母。因此，请告诉我，我如何才能继续前进，因为我无法得到解决办法，或告诉我在哪里的想法是
浏览 1提问于2018-06-27得票数 0
回答已采纳
2回答
KMP模式匹配算法的理论基础是什么？
我理解算法本身，但是，不知道Knuth，Morris和Pratt是如何发明这个算法的。
有没有什么数学证明？
你能给我一个链接吗？
浏览 4提问于2011-12-10得票数 17
回答已采纳
1回答
我知道我的问题类似于一些帖子，但我认为它有不同的方面。我正在寻找一个更大的数组中的子数组或模式。我将使用具有数千甚至数百万行的数组，我需要在该数组中找到一个模式。我要搜索的值与数组中的值相似。例如，我的10,000行数组将充满1、0、L和H，我将在其中搜索某个模式，例如，查找1 0 1 1 H。
从我所看到的，其他帖子上发布的大多数解决方案都是处理规模小得多的数组，并且子数组与源数组更不同。此外，当我在源数组中找到数组时，我需要返回该子数组的位置。(我希望用C#编写这段代码)
浏览 0提问于2013-03-13得票数 0
回答已采纳
我有一个n个字符串数组。我希望选择数组中的所有元素，其中has是给定的字符串。
抱歉，如果不清楚的话。我举个例子。
input = "as"
array = {"abas", "aras", "as", "ask", "asi", "aso", "atas", "best", "test"}
output = {"abas", "aras", "as", "ask", &#
浏览 3提问于2015-07-10得票数 0
回答已采纳
在这种情况下，有人能给我推荐最好的算法吗？或者这类操作的最佳技术。我知道如何通过将两个字符串与所有句子进行比较的基本方法。但有没有更好的方法。
浏览 16提问于2020-05-10得票数 0
我有两个列表，每个列表包含50个名字。
在两个列表之间存在满足以下条件的1-1对应关系:对于列表1中的每个姓名x，列表2中存在x的错误(或正确)拼写。
如果我有列表1，而我得到的是拼写错误的列表2，是否有可靠的算法将拼写错误的名称与拼写正确的对应名称进行匹配？
例如,
清单1:布什·奥巴马·特朗普
列表2: Burts Pbame Tramp
浏览 20提问于2019-07-10得票数 1
我熟悉这两种算法: Knuth Morris Pratt和Boyer moore。
给定一个字符串P，该字符串由具有大量字母的字母表组成。使用哪种算法更好？
给定一个具有二进制字母表(0或1)的字符串P。使用哪种算法更好？
浏览 3提问于2014-07-17得票数 2
5回答
查找字符串在另一个字符串中的位置
、、、、
可能重复：
给定两个字符串，A和B，如何找到B在A中的第一个位置？例如，A=“ab123cdefgcde"；B= "cde”，那么B在A中的第一个位置是5。
有没有什么技巧可以解决这个问题，或者从一开始就搜索A？
浏览 10提问于2010-03-03得票数 2
回答已采纳
我还想知道在查找一个字符串在另一个字符串中的所有匹配项的所有算法中，哪个算法的复杂度最差。似乎Boyer-Moore算法的时间复杂度是线性的。
浏览 2提问于2012-02-08得票数 11
回答已采纳
2回答
我要查找字符串S中与正则表达式R匹配的所有子字符串。正则表达式只能包含‘’。和符号(其中'.‘表示任何符号)。我正在尝试使用KMP来解决这个问题：
1)构建字符串T=R+ '#‘+S ('#’在这里是分隔符)
2)计算前缀-func。对于T
3)对于pi (prefix-func.共T)检查'#‘之后的位置，其中pii == len(S)。在这些位置，查找的子串结束。
而是前缀-func。将不能在包含'.‘的字符串上正常工作我的prefix-func代码：
pi[0] = 0;
for (int j = 0, i = 1; i < R.length
浏览 7提问于2014-04-10得票数 0
1回答
这是我实现的KMP字符串匹配算法。当我检查pi数组时，它存储0,1,2,3,4,5,6。但是根据algo书籍，它应该是0，1，2，3，0，1。我的代码也给出了正确的结果。我不明白为什么会发生这种情况，还是我做错了什么？如果是的话，请纠正我。
谢谢。
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int* ComputePrefix(char P[])
{
size_t m = strlen(P);
int *pi = new int[
浏览 1提问于2012-03-26得票数 1
回答已采纳
KMP (Knuth-Morris-Pratt)算法是否比简化的Boyer-Moore算法执行的比较少？
浏览 2提问于2010-11-24得票数 2
回答已采纳
1回答
许多关于KMP的文章都提到，KMP中的故障函数本身就有大量的应用。
一个这样的应用是寻找最小的字符串，当连接k次时，它给出了原始字符串(句点)。
但我找不到其他的。涉及KMP故障功能的其他问题有哪些？
浏览 1提问于2012-05-09得票数 5
回答已采纳
2回答
输入是两个字符串，第一个字符串是长字符串，第二个较小的字符串是置换字符串。
输出应该返回所有事件的起始索引以及较长字符串中子字符串的排列。
案件1)
permutationsInString('abcdcbadefbac', 'abc')
sample output: { '0': 'abc', '4': 'cba', '10': 'bac' }
案件2)
permutationsInString('abcabacba', 'abc'
浏览 0提问于2017-06-28得票数 3
回答已采纳
：Haystack: AAAAAAAAAA的解决方案是正确的吗？
因为，在干草堆里有8个AAA实例，然而据我所知，knuth-morris-pratt算法只会找到3个。我这样想是不是错了？
这个问题可以通过找出字符串中每个后缀的边界来解决吗？
下面是我对KMP算法的实现：
public static int occurrenceOfSubstring(char[] target, char[] pattern) {
int[] overlay = new int[pattern.length];
overlay[0] = -1;
overlay[
浏览 1提问于2014-01-29得票数 4
假设我有一个较大的byte[]，我不仅要查看较小的byte[]是否在较大的数组中，而且还要查看在较大的数组中的位置。例如：
byte[] large = new byte[100];
for (byte i = 0; i < 100; i++) {
large[i] = i;
}
byte[] small = new byte[] { 23, 24, 25 };
int loc = large.IndexOf(small); // this is what I want to write
我想我问的是在一个更大的序列中寻找任何类型的序列(原语或其他类型)。
我隐约记得在字符串中
浏览 0提问于2013-04-11得票数 3
回答已采纳
3回答
它看起来很简单，“从列表中的字符串中删除空格”。但出于某种原因我的代码不起作用。
new_list = []
channels = "KMP, PRIME"
channel = channels.split(",")
for each in channel:
re.sub(r'^[^a-zA-Z]*', ' ', each)
new_list.append(each)
我也尝试过lstrip/strip，但没有一种有效。为什么？如果我用下面的代码“欺骗”，它就会起作用。我还是想找出问题的真相。我该做些什么来弥补呢
浏览 0提问于2018-04-01得票数 0
回答已采纳
2回答
我已经实现了Knuth-Morris-Pratt算法来搜索字符串B中的字符串A。如果它找到字符串，如果返回字符串的第一个位置，则返回-1。但现在我想计算字符串A在字符串B中的总出现次数。
我已经尝试了一种简单的方法，它是有效的，但这似乎不是很有效，因为它需要大量的时间来处理大字符串。
有人能帮我解决这个问题吗？我想要一种使用KMP的更有效的方式。
这是我的测试。
public static int searchStringWithKnuthMorrisPratt(String s, String t)
{
int m=s.length();
int n=t.length
浏览 3提问于2013-07-02得票数 1
KMP算法需要一个前缀表，然后在失败后知道它可以安全跳过多少个字符。前缀表的一般思想是，它将告诉您对于给定的模式P，在给定的位置i和char C，直到C的后缀有多少个与P前缀相同的字符。
int[] T = new int[P.length()];
int i = 0;
for (int j = 1; j < P.length(); ++j) {
if (P.charAt(j) == P.charAt(i)) {
i++;
} else {
i = 0;
}
T[j] = i;
}
这就是我想出来的。我环顾四周，发现实现似乎总是不同的。我尝试了几个示例(例
浏览 0提问于2018-05-08得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
