问题标签 [longest-substring]

有谁知道解决最长常见子字符串问题的 R 包？我正在寻找可以在向量上快速工作的东西。

我正在寻找一个 Python 库，用于从一组字符串中查找最长的公共子字符串。有两种方法可以解决这个问题：

• 使用后缀树
• 使用动态规划。

实现的方法并不重要。重要的是它可以用于一组字符串（不仅仅是两个字符串）。

我在http://portal.acm.org/citation.cfm?id=1813708中实现了利用后缀数组查找最长公共子串的算法。该算法涉及为字符串构造一个后缀数组，该数组是一组给定字符串与称为哨兵的字符串分隔符的串联。例如，如果给定字符串 a、b 和 c，则会创建一个新字符串 d，它是 a$1b$2c$3，其中 $1、$2、$3 是标记每个字符串结尾的标记字符。标记字符必须是唯一的，并且在字典顺序上少于 a、b 和 c 中的所有其他字符。

我的问题围绕 Python 中哨兵字符的表示展开。如果 a、b 和 c 是 ASCII 字符串，我想我可能需要将这些字符串转换为 UTF-8 并将它们的范围从 0-127 转移到更高的范围，以便有可用的字符在字典上少于那些在字符串。如果这看起来合理，那么在 Python 中重新映射字符以使其范围为 N-127+N 的最有效机制是什么，其中 N 是提供的字符串数？

我想要一个给出列表的python函数

返回字符串'abc'，即列表中所有元素包含的最长片段。我有一个解决方案，它只遍历 的切片mystring[0]，并将其与其余部分进行比较，然后在找到第一个不匹配的子字符串时跳出循环。但是，我怀疑必须有一种更高效、更优雅、更 Pythonic 的方式来执行此操作。

有人能指出如何正确地做到这一点吗？

问题：

我有 3 个字符串 s1、s2、s3。每个都在两边包含垃圾文本，在其中心有一个定义模式：text1+number1. number1每个字符串增加 2。我想提取text1+number1.

我已经写了代码来查找number1

如何扩展 LCS 函数以获取 text1？

例子：

从"hello 5", "bolo 7","lo 9sdf"我想得到 "lo 5"

代码：

我已经能够编写一个简单的 LCS 函数（测试用例），但是我在编写这个修改后的函数时遇到了麻烦。

我试图在 ruby​​ 的字符串数组中找到所有常见的子序列，而不仅仅是最长的单个子序列。

这意味着如果输入是

[“aaaF 你好”，“aaaG 你好”，“aaaH 你好”]

预期的输出是

[“aaa”，“你好”]

我一直在搞乱最长的单子序列算法，但不知道如何获得适当的输出。大多数方法的问题是它们在最终数组中还有其他元素，例如“a”、“aa”、“h”、“he”、“hel”、“hell”

我终于像我想要的那样做了。谢谢大家的帮助，我想强调这不是家庭作业。

背景：

我正在开发一个程序，它遍历存储在我的计算机上的所有电影和电视剧集，对它们进行评分（使用烂番茄）并按评分顺序对它们进行排序。

我通过从文件名中删除所有不必要的文本（例如“.avi”、“720p”等）来提取电影名称。

我正在使用 Java。

问题：

某些文件夹包含电影文件，例如：

第301话热带雨林Schmainforest.avi

第302话自燃.avi

“剧集”这个词和数字是有效的，并且是电影中的常用词，所以我不能简单地删除它们。但是，从名称的重复性中可以清楚地看出“Episode”和“3XX”应该被删除。

另一个文件夹可能是：

720p.S5.E1.cripple Fight.avi

720p.S5.E2.towelie.avi

许多像这样的 任意模式存在于不同的文件组中，我需要一些东西来识别这些任意模式，以便我可以提取关键字。为每种情况编写正则表达式是不可行的。

概括：

是否有工具或 API 可用于查找复杂的重复模式（必须能够匹配数字序列）？[类似于最长的公共序列库]

任何人都可以帮助我优化我的 LONGEST COMMON SUBSTRING 问题吗？我必须读取非常大的文件（最大 2 Gb），但我不知道要使用哪种结构...在 c++ 中没有哈希映射。TBB 中有并发哈希映射，但使用起来非常复杂算法。我用 **L 矩阵解决了这个问题，但它很贪心，不能用于大输入。矩阵充满了零，这可以通过使用 map> 来消除，并且只存储非零，但这真的很慢并且实际上不可用。速度非常重要。这是代码：

当我看到一个问题询问我是否可以从字符串中找到最长的单词（字符串没有空格，只有字符）时，我已经开始研究一些算法问题。经过一段时间的思考，我只是想确认我是否可以使用动态编程来解决类似于最大连续和问题的问题。在解析每个字符之后，我可以调用 isWord 方法（已经实现），然后如果它继续转到下一个字符并增加单词长度，如果不是，那么只需将计数器重置为零并开始从该索引中查找一个单词. 请让我知道这是否是一个好方法，否则请指导我有什么更好的方法来解决这个问题。

谢谢你们的帮助。

-维克