问题标签 [subsequence]

给定一个字符串说S长度m 和一组其他R长度都等于或大于的字符串m。查找集合中具有S子序列的字符串。

因此，如果S是blr并且字符串集是：

它应该返回前两个字符串。

我知道我可以 在时间复杂度 O(n+m)中找到一个S长度字符串m是否是其他T长度字符串的子序列。n所以我知道我可以对集合中的每个元素执行此算法，但这将是 O(k*(n+m)) 的时间复杂度，k即集合的大小（并假设所有字符串都具有相同的长度）。这让我想知道是否有某种预处理可以帮助我用多个字符串解决这个问题。

那么，有什么预处理或结构可以用来解决这个问题吗？我能达到的最佳时间复杂度是多少？有没有其他方法可以解决这个问题？

我有一个长度为 1 的序列。也就是说，

现在我可以说longest increasing subsequence上述序列中长度为 1 的 是1。上面序列中longest decreasing subsequence长度为 1 的1?

最长递增子序列问题是找到给定序列的子序列，其中子序列的元素按排序顺序排列，并且子序列尽可能长。

这是我的 O(n^2) 方法，对于长输入运行非常慢：

谁能告诉我如何在 O(n*log n) 时间内完成？

我正在阅读有关 geeksforgeeks 的一些动态编程文章，并遇到了最长公共子序列问题。我自己并没有提出指数朴素解决方案的实现，但是在在纸上解决问题的一些示例之后，我想出了我认为是成功实现O(n*m)版本的方法。然而，OJ 证明我错了。我的算法因输入字符串而失败：

• "LRBBMQBHCDARZOWKKYHIDDQSCDXRJMOWFRXSJYBLDBEFSARCBYNECDYGGXXPKLORELLNMPAPQFWKHOPKMCO"
• "QHNWNKUEWHSQMGBBUQCLJJIVSWMDKQTBXIXMVTRRBLJPTNSNFWZQFJMAFADRRWSOFSBCNUVQHFFBSAQXWPQCAC"

我对算法的思考过程如下。我想维护一个 DP 数组，其长度是输入字符串a中a较小的字符串长度。dpA[i]将是以 结尾的最长公共子序列a[i]。为此，我需要遍历a索引中的字符串0 => length-1并查看是否a[i]存在于b. 如果a[i]存在，b它将在 position pos。

1. 第一个标记dp[i]好像1是dp[i]0
2. 要知道这a[i]是对现有子序列的扩展，我们必须遍历a并找到与后面的值匹配的第一个i字符。让我们分别调用这些匹配值的索引。这个值保证是我们以前见过的值，因为我们已经涵盖了所有并填写了. 当我们找到第一个匹配项时，因为我们正在扩展前一个以. 冲洗重复。bposjka[0...i-1]dpA[0...i-1]dpA[i] = dpA[j]+1a[j]

显然这种方法并不完美，或者我不会问这个问题，但我似乎不太明白算法的问题。我一直在看它这么久，我几乎无法再考虑它，但任何关于如何修复它的想法将不胜感激！

编辑

我认为复杂性实际上可能是O(n*n*m)

我有一个data.frame：

上面的 data.frame 表示这些序列：

我只想提取这样的非子序列：

是否可以提取不是任何其他序列的子序列的序列？

PS。这是制作第一个data.frame的代码。

S给定一个长度只包含小写英文字母的字符串n，我们要计算长度为 4 的回文子序列的数量。

回文子序列的总数可以通过 计算O(n^2) DP。但是如何按顺序计算长度为 4 的此类子序列的数量O(n log n)？O(n)

示例：“abcdbaadc”的答案为 4。 [索引 (1, 2, 5, 6), (1, 2, 5, 7), (3, 6, 7, 9), (4, 6, 7, 8) ]

任何提示或解释表示赞赏。

在 Java 中，如何获得索引可以是 10^5 位长的 BigInteger 的子序列。

示例：BigInteger 长度为 10^5。我必须找到索引 10^3 和 10^4 之间的子序列

我希望能够找到单调递减子序列末尾的索引，该子序列从列表的第一个索引开始，并且仅按连续顺序下降。例如，我可能有一个如下所示的列表：

x = [89, 88, 88, 88, 88, 87, 88]并且我希望能够返回5，因为它是子序列的最后一个元素的索引，其中该子序列[89, 88, 88, 88, 88, 87]中的每个数字都是单调递减并连续下降，从89列表的第一个索引开始。

例如，我有一个看起来像这样的列表：x = [89, 87, 87, 86, 87]. 我想返回0，因为它是唯一从第一个索引 (89) 开始并且连续单调递减的数字（即，列表中的下一个数字从第一个数字下降 2）。或者，如果我有一个看起来像这样的列表：x = [89, 90, 89, 88]，我想返回0，因为它是序列中唯一从列表的第一个索引单调递减的部分。

很抱歉解释的困难。预先感谢您的帮助！

在这个程序中，我想找到最长的回文子序列，但无法运行程序

我为每个案例写了评论

这个打印最长回文子序列的程序不起作用，当我运行它时，Windows 控制台在输入后停止工作。

我需要代码（或以下问题的代码片段或有关如何解决的提示）：

通过从s中删除一个或多个字符得到字符串s的子序列。字符串的子序列集s = abc是a, ab, ac, abc, b, bc, c,和空字符串（它是所有字符串的子序列）。

查找 s 的所有可能子序列并按字典顺序打印它们。

这就是我想出来的，但它不起作用：

结果：

输出： a ab abc b bc c

预期输出：a ab abc ac b bc c