问题标签 [longest-substring]

我有两个字符串，例如：

现在最长的后缀匹配是

使用 re 的解决方案是什么？

这是我为前缀匹配找到的解决方案：

我在这里找到了一个脚本，在查找最低公共子字符串时效果很好。

但是，我需要它来容忍一些不正确/缺失的字符。我希望能够输入所需的相似度百分比，或者指定允许的缺失/错误字符数。

例如，我想找到这个字符串：

大黄色校车

在这个字符串里面：

那天下午他们坐上了大黄校车

这是我目前正在使用的代码：

任何帮助深表感谢。

更新

PHP levenshtein 函数限制为 255 个字符，而我正在搜索的一些干草堆是 1000 多个字符。

我知道这是一个有点老生常谈的话题，但我已经达到了从已经回答的内容中获得的帮助的极限。

这是针对Rosalind 项目问题 LREP的。我正在尝试在字符串中找到最长的 k-peated 子字符串，并且已经为我提供了后缀树，这很好。我知道我需要用每个节点的后代叶子的数量来注释后缀表，然后找到具有>=k后代的节点，最后找到这些节点中最深的。从理论上讲，我已经准备好了。

我从以下资源中获得了很多帮助（哎呀，我只能发布 2 个）：

• 查找字符串中最长的重复序列
• 深度优先搜索 (Python)

我可以获取从根到每个叶子的路径，但我不知道如何预处理树，以便我可以从每个节点获取后代的数量。我有一个单独的算法，它适用于小序列，但它具有指数复杂性，所以对于较大的东西，它需要的时间太长了。我知道使用 DFS 我应该能够以线性复杂度执行整个任务。为了使这个算法起作用，我需要能够在不到 5 分钟的时间内获得最长的 k-peat 的 ~40,000 长度的字符串。

这是一些示例数据（第一行：sequence，第二行：k，后缀表格式：parent child location length）：

输出应该是CATAC.

使用以下代码（从LiteratePrograms修改）我已经能够获取路径，但是在更长的序列上仍然需要很长时间才能解析出每个节点的路径。

我想做的是descendants >= k在找到深度之前对树进行预处理以找到满足要求的节点。我什至还没有弄清楚我将如何计算深度。虽然我想我会有一些字典来跟踪路径中每个节点的深度然后求和。

所以，我的第一个最重要的问题是：“我如何预处理带有后代叶子的树？”

我的第二个不那么重要的问题是：“在那之后，我怎样才能快速计算深度？”

PS我应该声明这不是家庭作业或类似的东西。我只是一个生物化学家，试图通过一些计算挑战来扩展我的视野。

LCS 的并行计算遵循波前模式。这是比串行实现慢的并行功能。（我认为对角线的数量（平行）与行数（串行）与它有关）

这是串行功能

...以为我会添加测试功能

在包含 n 个字符的序列 S 中；每个字符可能在序列中出现多次。您想找到 S 的最长子序列，其中相同字符的所有出现都在一个地方；

例如。如果 S = aaaccaaaccbccbbbab，那么最长的子序列（答案）是 aaaaaaccccbbbb 即 = aaa__aaacc_ccbbb_b。

换句话说，任何出现在 S 中的字母字符都只能出现在子序列中的一个连续块中。如果可能，给出一个多项式时间算法来确定解。

我试图找到两个可比较类型的事物之间的最长公共子序列。我有算法，但我想通过递归方法调用将这些项目添加到列表中，但我不知道如何以这种方式将最后一个项目添加到列表中。

这是我的代码：

我正在尝试构建一个人工智能单元。我计划首先将感官输入（“观察”）收集到一个短期工作记忆列表中，不断形成在这个列表中找到的模式（“想法”），然后将这些想法提交到一个长期存储记忆中它们达到了相当大的规模，可能是七个连锁观察。对于任何哲学人来说，类似于洛克的人类理解论文，但这不会是白板。需要有一个编码的底层结构。

因此，我的问题是：

是否有/在哪里有一个很好的算法来动态合并或“模式化”这个不断增长的观察字符串的最大子字符串？例如：如果到目前为止给了我 ABCDABCABC，我想要一个 ABC 想法，D 和另外两个 ABC 想法；然后，如果观察到另一个 D 并将其添加到短期记忆中，我想要一个 ABCD 令牌、一个 ABC 令牌和另一个 ABCD 令牌。我不想使用 Shortest Common Substring，因为我需要在添加任意数量的字符后重新运行它。我想我更喜欢一些易于搜索/可修改的树结构。

这看起来像一个足够体面的解决方案吗？ http://www.cs.ucsb.edu/~foschini/files/licenza_spec_thesis.pdf。如果不出意外，我认为其他数据挖掘者可能会喜欢。

我正在尝试实现 2 个字符串的最长公共子序列。我的方法与这里发布的有点不同。我接近解决方案，但问题不大。请帮我。

我的问题：期望输出：metalica 电流输出：etallica

我的代码是：

我知道还有其他方法，但我尝试使用简单的方法来实现。请指出问题。

我需要找到 n 个字符串中最长的公共子字符串并在我的项目中使用结果。

java中是否有任何现有的实现/库已经这样做了？

我正在尝试在 C 中实现最长的公共子字符串算法，在阅读了下面的帖子之后，我真的对以下部分感到困惑：

现在，最大值是 LCP[2]=3，但它是针对 SA[1] 和 SA[2]，两者都以字符串 A 开头。所以，我们忽略它。另一方面，LCP[4]=2 用于SA[3]（对应于 B 的后缀 bc）和 SA[4]（对应于 A 的后缀 bcabc#bc）。所以，这是最长的公共子串。

我的 LCP 结果也与帖子示例不同。

https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays

字符串 A = abcabc

字符串 B = bc

字符串分隔符：'#'

后缀数组

[#bc，abc#bc，abcabc#bc，bc，bc#bc，bcabc#bc，c，c#bc，cabc#bc]

液晶面板

[-1, 0, 3, 0, 2, 2, 0, 1, 1]

或删除第一个元素

后缀数组

[abc#bc, abcabc#bc, bc, bc#bc, bcabc#bc, c, c#bc, cabc#bc]

液晶面板

[0, 3, 0, 2, 2, 0, 1, 1]

我看到 SA[3] 对应于bc，但 SA[4] 对应（我猜）对应于#bcbc。所以，这就是让我困惑的地方。

任何人都可以澄清这一点？谢谢！