问题标签 [longest-substring]

我正在寻找第一个公共子字符串的实现

使用最长的公共子串实现（并忽略标点符号），你会得到“我认为你很棒”，但我正在寻找第一个出现的公共子串，在这个例子中：

也许是一个实现，它生成并排序了所有常见子字符串的列表，我可以从中获取第一个。

编辑

被比较的标记将是完整的单词。寻找第一个最长的整个单词序列的贪婪匹配。（假设在方法中使用了后缀树，树的每个节点都是一个词）

假设我有一个 txt 文件，每一行代表一个字符串。有没有一些有效的方法来找出前 10 个频繁子串。

困难在于给定字符串的子字符串排列太大。给定一个N字符串长度，它有总C(N,0)+C(N,1)+..C(N,N)种类的子字符串。

================================================= [更新]

这个问题与“[a link] Algorithm to find the most common substrings in a string ”类似，但两者都不相同。不同之处在于我试图找出所有字符串中的前 10 个频繁子字符串，而它只是在 "[a link] 中找到一个字符串中最长的子字符串算法来查找字符串中最常见的子字符串以找到最常见的子字符串一个字符串" 这只是局部优化。

尽管通过“[a link]算法以查找字符串中最常见的子字符串”中的方法在所有字符串中不经常出现一个子字符串，但它可能是最频繁的。比如我有 10 个字符串，字符串最频繁 str1 sub_str1 --4 次
str2 sub_str2 -- 4 次 ..
str10 sub_str10

每个字符串中出现频率最高的子串不同，每个出现 4 次。有可能在所有字符串中都存在另一个名为 sub_minor 的子字符串，并且只出现 1 次。因此，这个 sub_minor 字符串出现频率最高，因为它出现了 10 次，超过了所有其他 sub_str 字符串。

all sub_str 都只是局部优化而不是全局优化，我的问题主要是全局优化，这与“[a link] Algorithm to find the most common substrings in a string ”不同

我去学校工作时学习python。本质上，我需要在字符串列表中找到最长的重复子字符串，如下所示。我一直在阅读这篇文章，并了解我应该做什么。

到目前为止，我的实现如下：

现在，当我调用我的函数时，假设['slide', 'glidb', 'flidt', 'cridz', 'bidr'] 我得到了'id'作为最长子字符串的正确结果。

但是，当我通过列表时，['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']我没有得到任何返回结果。我应该作为我最长的子字符串返回'blah'，但我还没有找到实现这一目标的方法。似乎我只能在列表的所有项目中匹配子字符串。我如何修改我的代码/逻辑以获得多次出现的最长子字符串？

谢谢你。

我找到了Longest Common Substring的算法。通常使用dynamic programming，使用大小为 的二维数组来完成，mxn其中m和n是所考虑的两个字符串的长度。

我将为这两个字符串构造以下​​矩阵。

M[i][j] = 1 if s1[i]==s2[j] else 0.

例如，如果字符串是：abcxy和pqaabx

矩阵如下所示：

1现在，我在从左上到右下方向的每个对角线中搜索 s 的最大连续序列。

其中的最大值就是答案。

我可以在不显式使用数组的情况下执行上述操作。时间复杂度仍然是O(M*N)。所以，不需要内存。

谁能指出我哪里出错了？

到目前为止我已经做到了

不幸的是，它只打印“d”而不是“bcd”。对我来说，“l2 = lcs(xs, ystr)”这一行似乎没有被执行，因为如果我在开头添加调试打印，它会打印出该函数没有被称为机智参数“bcd”和“bcd”，但我确信在 else 语句开始后值没问题。我将不胜感激任何帮助。

我想打印 LCS 问题的所有可能解决方案。

两个字符串 abcbdab 和 bdcaba 应该打印以下 3 个字符串：bdab,bcba,bcab。

C是根据算法取值的全局矩阵表，m，n是序列a，b的长度。

但是输出是出乎意料的。

我们有两个字符串a和b分别。的长度a大于或等于b。我们必须找出最长的公共子串。如果有多个答案，那么我们必须输出较早出现的子字符串b（早于其起始索引在前）。

注意：a和的长度b最大为 10 ⁶。

我尝试使用后缀数组查找最长的公共子字符串（使用快速排序对后缀进行排序）。对于有多个答案的情况，我尝试将所有公共子字符串推入堆栈中，这些子字符串等于最长公共子字符串的长度。

我想知道有没有更快的方法呢？

我正在使用这个程序来计算后缀数组和最长公共前缀。

我需要计算两个字符串之间的最长公共子字符串。

为此，我连接字符串，A#B然后使用这个算法。

我有后缀数组sa[]和LCP[]数组。

LCP[]最长的公共子串是数组的最大值。

为了找到子串，唯一的条件是在相同长度的子串中，字符串B中第一次出现的那个应该是答案。

为此，我维持 LCP[] 的最大值。如果LCP[curr_index] == max，那么我确保left_index子字符串 B 的 小于 的先前值left_index。

但是，这种方法并没有给出正确的答案。错在哪里？

鉴于以下情况，我可以找到最长的公共子字符串：

[出去]：

但是我如何确保最长的公共子字符串尊重英语单词边界并且不切分单词？例如，以下句子：

输出不需要的后续内容，因为它分解了kappas2 中的单词：

所需的输出仍然是：

我还尝试了一种 ngram 方法来获取关于单词边界的最长公共子字符串，但是还有其他方法可以在不计算 ngrams 的情况下处理字符串吗？（见答案）

我正在尝试提取相同代码的（长）重复块，并在需要时让常规的执行流程跳转到这些块/从这些块跳转。
这是通过一种名为 Hack 的教育汇编语言完成的。
我怎样才能提取这些块。
我知道这是最长公共子序列问题的一个实例，但我不知道如何解决这个问题。
我见过，这个，这个，还有其他几个——没有帮助。

任何指针，无论是解决方案课程、相关阅读，甚至是库 - 都非常感谢。