问题标签 [knuth-morris-pratt]

此代码是在字符串中查找匹配模式的一部分。（KMP 算法）

我想一次只使用 32000 字节的字符串。

因此，如果字符串的大小大于 32000，我将它们拆分并计算“num”，即循环数。（例如，当大小为 64000 时，我必须运行该函数两次才能搜索整个字符串）

lsize 是线程号（实际使用openCL），l_length 是每个线程将搜索的分割字符串的大小。

问题是必须不搜索某些字符串，因为在分割功能期间丢失了大小。（例如，size = l_length*lsize/num && tmp_size = size/lsize）

我试图更改代码，但找不到每个线程的适当长度。（另一种用于查找分割字符串之间模式的代码已经存在。）

我该如何解决？

我在 PHP 中有一个 KMP 代码，它可以在单词到文本之间进行字符串匹配。我想知道是否可以使用 KMP 算法进行文本到文本之间的字符串匹配。有没有可能？以及如何使用它来查找 2 个文本之间的字符串匹配。

这是KMP算法的核心：

如果我想在文本上查找单词，我将这个类调用到我的 index.php 中。

这是我希望我的代码执行的步骤：（1）。我输入文本 1 (2)。我输入文本 2 (3)。我希望文本 1 成为模式（文本 1 中的每个单词都被视为模式）（4）。我希望我的代码可以在文本 2 (5) 中的文本 1 上找到每个模式。最后，我的代码可以告诉我相似度的百分比。

希望大家能帮助我或者教教我。我一直在到处寻找答案，但还没有找到。至少你可以教我。

我正在尝试使用模式匹配算法实现抄袭检测软件。我在这里遇到了KMP 算法并尝试了 c# 实现。我可以看到实际文档的速度并不快（不是字符串，我使用 iText 上传了两个 pdf 文档，并在这两篇论文中得到了检查抄袭的实现。大约 50 页）。

这真的很慢，我不知道该怎么做。我也看过Boyer Moore和Rabin Karp。

我目前正在做的是获取文档中的每个句子（拆分为“。”）并扫描整个参考文档（第二个文档）以进行匹配。然后接下一句话，依此类推……我完全知道这可能非常昂贵。但我不知道如何在不使用这种方法的情况下实现字符串（模式）匹配。这是我最后一年的项目，我得到了一个主题，所以我必须使用字符串匹配。（不允许做基于引用的抄袭、语义或向量空间。）

文本和模式越大，算法越慢（非常慢，甚至不是相当慢）。还有另一种我不知道的方法吗？还是有更快的算法供我使用这种我的方法？

编辑

我的代码如下：`

如果我的模式是“Brudasca”，那么 KMP 前缀表将全部清零。在那种情况下，KMP 和平凡的解决方案之间是否有任何性能差异？这不是 O(n*m) 的最坏情况吗？

我正在通过此链接阅读有关 KMP 的信息：（http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/）。

除了在相应链接中给出的以外，我已经实现了 KMP，它也给出了正确的答案，有人可以告诉我这种 KMP 的实现是对还是错？如果错了，那么请解释一下。

以下是我的实现：

I am trying to find patterns in a sequence of integers. I have found the KNUTH-MORRIS-PRATT (KMP) in this link.

I've fed the function a 'pattern' to find in a 'text.' But the output of the KMP function is an object. I need the indices for the instances of the pattern in the text. I tried checking out the attributes of the object by typing dot and pressing tab but nothing is there. How can I get the indices?

Edit

Code:

我在 CLRS 自学问题 32-1；c) 部分介绍了以下字符串匹配算法：

这里，ρ'(P)，它只是 P 的函数，被定义为最大整数 r，使得某个前缀 P[1..i] = y^r，例如重复 r 次的子串 y。

该算法似乎与简单的暴力字符串匹配器有 95% 的相似性。然而，让我非常困惑的一个部分，似乎是整个算法的核心，是倒数第二行。这里，q 是到目前为止匹配的 P 的字符数。背后的原理是ceil(q/k)什么？这对我来说是完全不透明的。如果该行类似于s = s + max(1+q, 1+i)，那将更有意义，其中 i 是产生 ρ'(P) 的前缀的长度。

CLRS 声称该算法归功于 Galil 和 Seiferas，但在他们提供的参考资料中，我找不到与上面提供的算法相似的任何东西。如果有的话，参考似乎包含这里的更高级版本。有人可以解释这个ceil(q/k)值，和/或指向描述这个特定算法的参考，而不是更知名的主要 Galil Seiferas 论文吗？

我想知道哪种算法用于将模式与标准库中的字符串进行匹配。如果要在同一字符串中执行更多搜索，则后缀树将是最佳选择。

是后面的数据结构std::string::find()还是像 Knuth-Morris-Pratt 算法这样的 one-shot 算法？

KMP 算法需要一个前缀表，以便在失败后知道它可以安全地跳过多少个字符。前缀表的一般思想是，它会告诉您对于给定模式P，在给定位置i，带有 charC的后缀有多少个公共字符，C前缀为P：

这就是我想出的。我环顾四周，实现似乎总是不同的。我尝试了几个示例（例如 ABABACA），但是我的实现和例如这个KMP 前缀表似乎都产生了相同的结果。

谁能告诉我我的实现中的逻辑错误是什么，以及在为 KMP 算法生成正确的前缀表时会失败的输入是什么？

谢谢

给定一个模式abababc，前缀表是[0,0,1,2,3,4,0]。但是， at ababab、abab和ab都是前缀。为什么我们只将abab其视为有效前缀？

我想不出一个较长的前缀会失败但较短的前缀会起作用的例子。有没有证据表明应该只考虑最长的前缀？谢谢！