问题标签 [longest-substring]

我有一个字符串

Millett Angle-Loc Weaver Extension 1 inch Rings, Black, Medium, Front/Rear Exte

我想从中提取 "Millett Angle-Loc Weaver Extension 1 inch Rings, Black, Medium, Front/Rear" ，String即最后一个" "（空格/空白）（或右起第一个）之前的子字符串。

有人可以提供一些帮助吗？

在这之后我完全脑筋急转弯，我需要找到两个文件之间最长的公共子字符串，一个小文件和一个大文件。我什至不知道从哪里开始搜索，这是我到目前为止所拥有的

到目前为止，我所做的是将每个文件放入一个字符串生成器中，然后放入一个字符串中以消除双空格（它在 MobyDick.txt 上出现了很多）。我找到了这段代码

此代码有帮助，但仅适用于小文件，每次我使用大文件运行它时，都会出现“内存不足：java 堆空间”错误。我需要正确的算法来摆脱堆空间问题，而且我不能增加 java 内存，任何人都可以帮助或指出正确的方向吗？

python中是否有一个内置函数可以返回两个列表的最长公共子序列的长度？

我试图找到最长的公共子序列，然后得到它的长度，但我认为必须有更好的解决方案。

最近我正在学习如何使用树来解决最长公共子串问题。在从 Wiki 和其他在线资源学习之后，我发现我们应该使用后缀树来查找最长公共子串。

正如维基所说：

一组字符串的最长公共子串可以通过为字符串构建一个广义后缀树，然后从它下面的子树中的所有字符串中找到具有叶节点的最深内部节点来找到

正如贾斯汀所说：

在（紧凑）后缀树中，您需要从所有字符串中找到具有叶节点的最深内部节点。如果在同一深度有多个节点，则必须比较该节点表示的字符串的长度。即ABC、BC、C都有相同的深度，所以要比较ABC、BC、C字符串的长度，看哪个更长；这显然是ABC。

在这里，我认为从所有字符串中查找具有叶节点的最深内部节点的过程实际上是从所有字符串中查找所有后缀的最长公共前缀的过程。

所以这里有一个问题：为什么我们不构建前缀树来存储所有字符串的所有后缀？然后我们可以搜索前缀树来找到这些后缀的最长公共前缀。我无法分辨这两者之间的区别。谁能给我一些线索，为什么我们使用后缀树而不是前缀树来解决这个问题？

I wanted to compare the LCS of two files from their binary, therefore i used the usual LCS source code, and using the GenStr command to change the bytes of the file to String first. The problem is, I received memory out of bound error because comparing String has limit, therefore i am planning to use array that stores the bytes then compare it. Is it possible to use LCS algorithm to compare two arrays of bytes?

EDIT:

I tried, but haven't been able to check if this can be used or not, because of some errors.

Questions:

1. how do you append the lcs in line (return result) and line (return result_new)?
2. how do you clear the array so i can use it over and over again with different input? (Array.fill(D_new, null) and Array.fill(L_new, null) doesn't work)?

Thank you in advance

我有一个从论坛抓取到数据框中的文本消息集合。这是一个可重现的示例：

我的想法是在同一作者的每条消息中找到最长的共同后缀，这些后缀是所有那些写了超​​过消息的人。对于所有其他人，好吧，我会找到一种优雅地降级的正则表达式方式。

由于函数 getLongestCommonSubstring，我发现看起来很有希望的 bioconductor 包 RLibstree，但我不知道如何将该函数分组到来自同一作者的所有消息。

我正在寻找两个不同字符串的子字符串；问题如下：

给定两个字符串 x = X1...Xn 和 y = Y1...Ym，找到最长公共子串的长度，以及在索引 i 和 j 中的最大 k 与 XiXi+1...Xi+k -1 = YjYj+1...Yj+k-1。展示如何在 O(m*n) 时间内做到这一点。

有人可以帮我解决这个问题，我已经研究了太久了？我已经尝试过为这个问题做子空间，但最终弄错了。任何帮助将不胜感激！先感谢您！

编辑：向上

该代码不能与下面的字符串一起正常工作。

编辑：我注意到，如果我在第二个字符串中将 20 更改为 40，则该函数可以正常工作......

对于字符串：

它工作正常。哪里有问题？

这是我的代码：

此代码的输出（对于前两个字符串）是：

但是，输出应该是：

我正在尝试使用自下而上的动态编程编写两个 String 对象的 LCS。我能够让它与O(mn)空间一起正常工作。但是，正如我所见，我不需要前面的所有列。因此，我尝试对其进行修改以使其适合 2 列，因此空间变为O(m). 但是，它不适用于所有输入（例如，对 this:abcabc和abcbcca）。我在这里想念什么？不是硬件，不是竞赛。练习DP。

我正在尝试在 python 中使用递归来实现这个函数，但我有一个错误。我不明白是什么错误，你能帮帮我吗？

编码：

输入：

预期输出：5
我得到什么：4