问题标签 [longest-substring]

好吧，我的问题是：我必须返回两个给定字符串之间较大序列的大小。

我目前的代码：

一些输入及其预期输出：

• abcdef cdofhij // 2 (对 ("cd")
• 二四// 1（字母“O”）
• abracadabra open // 0（无）
• Hey This java is nice Java is a new patterns // 7 ("ava is ")

上面的所有输入都与我的代码完美配合，但在某些情况下仍然失败（可能是因为它有重复的字母，我不知道）..

错误输出示例：

• abXabc abYabc // 它应该输出 3，但返回 4

所以，我现在被困住了，任何帮助表示赞赏。

我有两个包含城镇名称的向量，两者格式不同，我需要将水区（水）的名称与其各自的人口普查数据（城镇）相匹配。基本上对于水中的每一行，我需要知道城镇中的最佳匹配，因为它们中的大多数都包含类似的词，例如城市。我看到的另一个问题是单词在一个数据集中大写，而在另一个数据集中没有大写。这是我的示例数据：

我构建了一个查询来查找列的最长公共子字符串并按频率对它们进行排序。我遇到的问题是删除/分组类似的结果。

这是下面代码的 TOP 5 输出 - 请注意“I love mittens the cat”是最长、最频繁的字符串，但该代码还会找到该字符串的所有子字符串，例如“I love mittens the ca”或“I love手套 c"。

如果可能的话，我想删除任何与其他包含部分单词的子字符串相似的子字符串。第 3 行会很好，因为它都是完整的单词，但第 4 行和第 5 行应该被删除，因为它们与第 1 行相似。

我正在尝试使用递归和 DP 找到两个字符串的最长公共子字符串。请注意，我指的不是最长连续子序列。所以，如果两个字符串是

我正在尝试使用递归和回溯来做到这一点。但是，问题是，如果我使用如下递归，+1会在帧中预先添加，即在调用堆栈中更高，并且不知道要出现的字符是否确实是连续元素。因此，按照上面的例子，“bcdf”就是答案。

至于现在，下面的代码是我想出的。请注意，每次发现不匹配时，我都会将计数重置为 0。并使用名为int count的变量跟踪匹配字符的数量，并使用名为int maxcount的变量记录程序中任何点的最高值。我的代码如下。

这工作正常。但是，我不喜欢我的代码的几件事

1. 使用全局变量（静态 int maxcount）跨帧进行比较
2. 我不认为这是真正的动态编程或回溯，因为较低的帧没有将其输出返回到较高的帧，然后决定如何处理它。

请给我您的意见，说明如何在不使用全局变量和使用回溯的情况下实现这一目标。

PS：我知道解决该问题的其他方法，例如保留矩阵并执行类似的操作

M[i][j] = M[i-1][j-1]+1 如果（str[i] == str[j]）

目标不是解决问题，而是找到一个优雅的递归/回溯解决方案。

我正在尝试解决Ruby中最长的回文问题，我在stackoverflow上找到了答案：

回答：

假设字符串有 n 个字符。首先看看整个字符串是否是回文。如果是，则返回字符串。菲尼！如果不是，请查看长度为 n-1 的两个子串中的任何一个是否是回文。如果有，请退回。如果不是，则检查长度为 n-2 的子串，依此类推。只要字符串包含至少一个字母，就会找到最长的回文。

但我无法理解这一行：

做什么

意思是？

还有为什么这行不通？

当我运行它时，它给了我

但是我不明白为什么当我检测到第一个满足条件的数组时 ana 会是 ["r", "a", "c", "e", "c", "a" , "r"] 所以这不应该在 ana 中吗？

我需要一些有关此功能的帮助。我试图找到 2 个字符串之间最长的公共字符串。这是我目前正在使用的功能：

这对大约 600 个单词左右的字符串非常有效。如果我尝试比较字数大于字数的字符串，它会开始抛出system.outofmemoryexception。显然，这对内存造成了很大的打击。有没有办法微调这个功能，或者是否有另一种更精简的方法？

我是第一次研究这个算法。CLRS (15-4.6) 要求编写一个算法以在 O(n lg n) 时间内运行。我想出的算法似乎在 O(n) 中运行。我想我一定是误解了一些东西，因为即使是维基百科也说它应该花费 O(n lg n) 时间。（https://en.wikipedia.org/wiki/Longest_increasing_subsequence）
有人能告诉我为什么这个算法（在 Python 中）不能正常工作或者不是 O(n) 或者不能回答这个问题吗？

寻找最长重复子串的算法公式如下 1)build the suffix tree 2)find the deepest internal node with at least k leaf children 但我不明白为什么这是有效的，所以基本上是什么让这个算法正确？另外，我发现这个算法的来源说是在 O(n) 中找到重复的子串，其中 n 是子串的长度，这对我来说也不清楚！让我们考虑下面的树，这里最长的重复子串是“ru”，如果我们应用 DFS，它将在 5 步中找到它，而不是在 2 步中你向我解释这些东西？谢谢

图片

我正在处理的问题在这里： http: //practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

基本上我们得到了两个字符串，我们被要求找到最长的公共子序列。我在网上搜索了解决方案并将它们与我自己的解决方案进行了比较，但我在我的代码中找不到任何错误。我想知道为什么它仍然不起作用。

而且，我被要求通过使用递归方法来解决这个问题

这是我的代码：

以下是所有测试用例：

调用值返回

“ABCDEFG”、“BGCEHAF”、“BCEF”

“她卖”、“贝壳”、“卖”

“12345”、“54321 21 54321”、“123”

《白眼老师》、《好吃的桃子》、《各显神通》

“马蒂”、“海伦”“”

"","乔" ""

“苏西”、“”“”

“ACGGTGTCGTGCTA”、“CGTTCGGCTATCGTACGT”、“CGGTTCGTGT”

使用我的代码，我得到了所有测试用例的 StackOverFlow。

我对 Python 很陌生，它是我的第一门编程语言，我一直想从事一些手动数据结构操作和玩耍。

我最近一直在学习解决 LCS 问题的基本算法，并且我了解它是如何工作的，除了一行代码，我出于某种奇怪的原因似乎无法说服自己我完全掌握了。

这是我在自己无法完全正确理解之后一直用来学习的代码。

编辑2：无论如何，要使用两个整数列表的输入来完成这项工作？**我发现我正确理解了我的原始问题，但有人知道我如何使用**整数列表来完成这项工作吗？我尝试将 S 和 T 转换为逗号分隔值的字符串，这可以匹配某些字符，但即便如此，它在大多数测试用例中也很少起作用。我不知道为什么它不会，因为它仍然只是比较两个字符串，但是用逗号。

现在我的问题是理解这一行：lcs_set.add(S[i-c+1:i-1])

我知道当找到匹配项时计数器会增加，以提供最长的子字符串长度。因此，为了简单起见，如果 S = Crow 且 T = Crown，当您到达 w（最后一场比赛）时，计数器将递增到 4，并且 i 在 S 的索引 3 处。

这是否意味着我将其读作：i（S 上的索引 3，W）-c（4），所以 3-4 = -1，所以 3-4+1 = 0（在 C 处）和右侧切片的：i(3) + 1 = 4(N，但显然不包括在内)，这意味着我们以 S[0:4], Crow, to LCS_Set 结尾？

如果是这种情况，我想我很困惑为什么我们将整个子字符串添加到集合中，而不仅仅是最新匹配的字符？

如果我理解正确，它会用当前匹配的子字符串的整个切片更新LCS_set ，所以如果它在第二个匹配项 R 上，计数器将为 2，我为 1，它会说 S[ 1-2+1:i(1)+1]，所以 1-2 = -1, -1 + 1 = 0(C) 直到 i(1)+1 = 2（留下 S[0:2 ] 或 CR)，因此每次都会使用整个子字符串更新集合，而不仅仅是当前索引。

这不是一个真正的问题，我只是想确保我正确理解这一点。

我真的很感激任何输入，或者任何人可能会用我当前的逻辑看到的任何提示！

编辑：

我刚刚意识到我完全忘记了 C 的位置是当前的计数器编号，因此它显然不会用当前的最大匹配数更新 LCS_set，它不能只用当前匹配的字母来更新它，所以它必须获取子字符串的切片才能更新 LCS_Set。提前致谢！