问题标签 [longest-substring]

给定“abcabcbb”，答案是“abc”，长度为 3。

给定“bbbbb”，答案是“b”，长度为 1。

给定“pwwkew”，答案是“wke”，长度为3。注意答案必须是子串，“pwke”是子序列而不是子串。

我想出了一个可行的解决方案，但在几个测试用例中都失败了。然后我找到了一个更好的解决方案，我重写了它以尝试理解它。下面的解决方案完美无缺，但经过大约 2 个小时的与这件事的斗争，我仍然不明白为什么这行特定的代码行得通。

有问题的行是

我不明白为什么会这样。我们取上一个最大值之间的最大值，以及我们当前索引和当前最长子字符串的起始索引之间的差异，然后加 1。我知道代码正在获取我们当前索引和startingIndexOfSubstring，但我无法概念化为什么它可以为我们提供预期的结果；有人可以向我解释这一步，特别是为什么它有效吗？

为了解密消息，我需要首先找到密钥。从给定的信息中，我发现键是字符串的一部分：

str = "251220825122082"

我们可以很容易地得到密钥应该是“ 2512208”，因为密钥应该被重复用于加密消息。但是，我尝试了很多方法，得到了答案“ 25122082”，最后又加了一个2，但这只是关键的另一个开始。

我试过的方法：

1. 正则表达式：String repeated = str.replaceAll("(.+?)\\1+", "$1");
2. LRS Java

这两个提供相同的答案（“ 25122082”）。

谁能帮我解决这个问题？

谢谢！

我想在 PHP 中找到 2 个 URL 之间的共同模式。我已经玩过https://gist.github.com/chrisbloom7/1021218但这在找到最长的匹配时停止，而不考虑 URL 中存在的通配符。

例如这里有 2 个 URL

• http://example.com/collections/dresses/products/dress.html
• http://example.com/collections/shoes/products/shoe.html

如果我在这些上运行函数，我的常见模式是

我正在寻找的是

有谁知道我可以如何调整代码以使其工作，或者有更好的方法吗？

我的输入字符串是

1. inputData = "99998UNKNOWN"
2. inputData = "01000AMEBACIDE/TRICHOM/ANTIBAC 1"
3. inputData = "34343AMEBACIDE/TRICHOM/ANTIBACSADWA1"

ID = inputData.Substring(0,5); Name = inputData.Substring(5,30); Level = inputData.Substring(35,1);

我收到以下错误，索引和长度必须引用字符串中的位置。

我可以理解，错误是由于“名称”的子字符串中指定的长度与第一个输入不匹配。有没有办法用任何输入长度来处理这个问题？

我编写了以下 Java 代码来搜索一对字符串之间共有的最长子字符串。代码如下：

当我用这些字符串测试它时，程序返回正确的字符串 dist，但是当我将字符串更改为：

我得到一个索引越界异常。还进行了以下更改：

结果我得到了字符串cttttt，但它应该只打印ttttt。有什么帮助吗？

谢谢

有两个要匹配的列表，li_a给定的列表由句子的字符序列组成，而给定的列表li_b是单词的集合。

该过程是li_a迭代地匹配项目，与li_b项目。如果 的第一个字符与项目li_a相似，则将 的第一个字符与下一个字符连接，并重做该过程，直到达到最长匹配。然后，最长的任期应该被拆分，这个过程将一直持续到最后。由于未出现的未知字符和单词将照常附加。li_bli_ali_ali_b

最后的工作应该是这样的：

到目前为止的尝试，但这适用于两个字符串而不是Lists，并且它不会检索未识别的单词。

我有两个字符串

str1 = "bqdrcvefgh"

str2 = "abcvdefgh"

我想找到两个字符串之间的 LCS。但我遇到字符串索引超出范围异常。这是我的代码

我究竟做错了什么？

PS-正确答案是7

在我的 Swift 3.0 应用程序中，我想通过查找 6 到 12 个字符串的最长公共子字符串来确定某事物的最佳名称。

示例字符串：

期望的输出：

对于最长的子序列，我遇到了多个 StackOverflow 答案，但无法根据我的需要调整它们中的任何一个。

任何帮助将不胜感激！

我的问题类似于找到最长的重复非重叠子字符串，但以这种方式。例如，我的输入数组是0,0,0,1,2,1,1,2,1,1,2,1,2,0,0

此输入中最长的重复且不重叠的子字符串121的计数为3 Now，121从输入数组中删除出现的 并将其替换为-1。

我的输入现在变为：0,0,0,-1,-1,-1,2,0,0 现在再次找到相同的子字符串。

注意：答案中不应包含-1。因此，下一个最长的非重叠和重复子串是00count as 2。

从输入中删除出现的 0,0，然后变为：0,-1,-1,-1,2,-1 现在唯一出现的是长度为 1 的 0 和 2。所以，我们在这里停止。

我只能想到 O(n ³ ) 的蛮力。也尝试过考虑后缀树，但不知道如何在其中包含非重叠条件。

我非常天真的实现：

因为我希望我的子字符串的计数至少为 2，所以它的最大长度可以为 N/2（N 是输入数组的大小）

如上所示，复杂度为 O(N ³ )。

任何最佳解决方案、提示或解释都会有所帮助。

谢谢

所以我最近在一次采访中得到了这个问题：

给定一个字典和一个起始字符串，通过在输入字符串的前后添加一个字符可以形成的最长单词是多少，并且每个新单词也必须出现在字典中？

例如：input = 'at' Dict = {hat, chat, chats, rat, tat, tats, chatats}

返回“聊天”，因为：在 -> 帽子 -> 聊天 -> 聊天

我想到了一个解决方案，我们暴力破解并尝试将 a - z 的所有字母添加到输入字符串的前后，如果存在新字符串，那么我们再次暴力破解这 26 个字母，最终得到最终的字符串。

我想知道是否有更有效的方法来解决这个问题，而无需每次都强制所有 26 个字母前后移动？

我想到的一种方法是遍历字典，如果输入字符串作为长度大于更改输入字符串长度 1 的任何条目的子字符串存在，则从条目字符串中删除输入子字符串。

例如：在第 1 次迭代之后，dict 将是 = {h, chat, chats, r, t, tats, chatats}

我们还将为每个条目设置一个长度变量来跟踪条目的原始长度。但我不确定这是否是正确的方法/甚至会起作用。