问题标签 [longest-substring]

我收集了一些作者的文章。每个作者都有一个独特的签名或链接，出现在他们的所有文本中。

作者 1 的示例：

Author1 的预期输出为：@jhsad.sadas.com

作者 2 的示例：

Author2 的预期输出为：

请特别注意没有可靠的识别字符（或位置）来表示签名的开始或结束。它可以是 url、Twitter 提及、任何类型的纯文本等，任何长度，包含出现在字符串开头、结尾或中间的任何字符序列。

我正在寻找一种方法，该方法将提取$text单个作者的所有元素中存在的最长子字符串。

为了这项任务，预计所有作者都将有一个签名子字符串，该子字符串存在于每个帖子/文本中。

IDEA：我正在考虑将单词转换为向量并找到每个文本之间的相似性。我们可以使用余弦相似度来找到签名。我认为解决方案一定是这样的想法。

mickmackusa 的注释代码捕获了所需内容的本质，但我想看看是否有其他方法可以达到预期结果。

我有以下输入：

• 公差水平 T
• 数字数量 N
• N个数字

任务是在这 N 个数字中找到最长的周期，使它们在容差范围内。更准确地说，给定子字符串的左右边界l和r两个不同的元素a1，并且a2在这两个边界之间，它必须保持|a1 - a1| <= T. 我怎样才能有效地做到这一点？我的做法是：

编辑：说清楚。该代码按预期工作。但是，它的效率不够高。我想更有效地做到这一点。

Skiena 的算法设计手册问题 8-3 b 部分要求给出一个“更简单”的 BigO(nm) 算法，用于查找不依赖于动态编程的最长公共子串。显而易见的答案似乎是使用后缀树，但是，Skiena 使用“更简单”这个词简单的。所以，我想知道，有没有另一种方法可以在 O(nm) 时间内解决这个问题？

我正在尝试了解此代码在幕后的工作原理，感谢您的帮助

请解释这部分：

=================================================

My current implementation is this:

Some examples of what I'm trying to do:

Mostly, I'm looking for efficiency here. The current implementation works, but I've been told it's O(m^2 * n), which is pretty bad.

Thanks in advance!

我知道有针对 rosalind 挑战的解决方案，但我不希望它们破坏乐趣。我以为我找到了“寻找共享主题”的解决方案，但我的答案一直都是错误的。

问题是关于在给定工作表中找到最长的公共子字符串，该工作表由以“>”开头的行和下一行直到另一行以“>”开头的行组成一个序列。这是它的样子：

大约有一百个 dna 片段，你要找到最长的公共子序列。这是我的方法：

我的策略是；读取文件，将其拆分为序列，选择第一个序列并将其公共部分与其余部分进行比较。我正在检查至少 2 个匹配项，因为序列由 ATGC 组成，并且肯定会发生 1 个匹配项。它从一个字符开始，并继续将其扩展 1 个字符，直到匹配被破坏。然后它获取最后一个匹配位并附加到一个列表中。然后从它停止的地方重新启动。

我的解决方案给出了答案，但它不是正确的，我无法发现代码中的误导部分。有人可以尝试了解我的方法并就修复它给我建议吗？

假设我有 2 个大小为 10^5 的大字符串，我如何使用哈希和二进制搜索从复杂度为 O(NlogN) 的两个字符串中搜索最大公共子字符串。用代码解释会有很大帮助:)

为什么指针 X 和 Y 必须在 lcs 函数中传递？当传递数组而不是指针时，还有什么问题。

}

找到一个共同的子串已经在许多问题中得到解答，即给定一个字符串列表，找到对所有字符串都通用的（通常是最长或最多的单词）子串。看这里：

来自两个以上字符串的最长公共子字符串 - Python

我的问题是，如何在字符串列表中找到最长的模态子字符串？这里重要的规定是这个子字符串不一定要出现在列表中的所有字符串中。

这里的科学有一点艺术性，因为明显的权衡是在 1）您希望子字符串出现在多少个字符串中？和 2) 你希望子字符串有多长？为了解决这个问题，让我们假设我们希望所需的子字符串包含三个单词（如果此处出现平局，则取最长的字符串，然后是第一个实例）。

所以给定清单，

所需的输出是，

如果规定是两个字长，那么所需的输出将是，

因为“that thing”是一个比“how's it”或“it going”更长的字符串

代码中的上述答案分别是三个和两个单词长的模态子字符串。

编辑：

由于对此有赏金，我将更具体地说明模态子字符串是什么。

模态子串：对于子串中给定长度的单词（这是唯一标识模态子串所必需的），模态子串是列表中最大数量的字符串共有的子串。如果存在平局（即对于给定长度的子字符串中的三个单词，有两个候选子字符串都出现在 80% 的字符串中），则应使用具有最长字符长度的子字符串。如果在那之后仍然存在平局（这应该不太可能但很好解释），那么只需选择第一个或随机选择。

一个好的答案将有一个函数，该函数返回子字符串中给定数量的单词的模态子字符串（其中单词的数量可以是任意数字）。

一个令人难以置信的答案将免除“给定单词数”的限制，而是包含一个标量（例如 \alpha），它管理子字符串长度（以单词为单位）和它出现在列表中的次数之间的权衡。接近 1 的 Alpha 将选择一个非常长（以单词表示）但不一定在列表中出现多次的模态子字符串。接近 0 的 Alpha 将选择在列表中出现尽可能多且不关心子字符串长度的模态子字符串。不过，我并没有真正期待这一点，并且会接受一个回答原始问题的答案。

出于交互式解析的目的，给定一个输入字符串，我需要提取从索引 0 开始并且只有匹配括号的最长子字符串。

示例（类似 LISP 的 s 表达式）

输入字符串：(print "hello") (assign a (+ c d)) (assign e (+ f g)

输出子串：(print "hello") (assign a (+ c d))

我想做一个简单的 Python 函数来实现这一点。