问题标签 [subsequence]

我有一个字符串（不包含换行符），我想找到第一个字符串中的另一个字符串的所有子序列。

例如，假设我要查找的字符串是"hello world". 如果我在这个字符串中搜索（使用正则表达式）它："1h2e3l4l5o6 7w8o9r0l0d0"，它应该能够发现它确实包含（一次）字符串"hello world"。它还应该能够在以下字符串中找到多个匹配项："hheelloo wwoorrlldd".

我有以下代码：

这行得通。有点。如果stringToSearch是"1h2e3l4l5o6 7w8o9r0l0d0"，它工作得很好。但是，如果stringToSearchis "hheelloo wwoorrlldd"，那么这个正则表达式只能找到一个匹配项，这是错误的。

关于如何解决这个问题的任何想法？

在 Cormen 的算法一书中，它给出了一种寻找最长子序列的算法。填充表格时，它从右下角而不是左上角开始：简而言之，它从两个序列的最后一个元素而不是第一个元素开始寻找两个序列的最长子序列。这背后是否有一个绝妙的理由（更高效等）？

例如让我们采取序列

我希望正则表达式匹配所有子序列，包括重复字符。这意味着子序列的总数应该是 5，而不是 3。

澄清：

让我们计算我们的角色。我们的序列看起来像

所有子序列为：

我可以在正则表达式中做到这一点吗？我目前正在用 Java 编程，我知道可以在那里开发一种算法，但我现在想避免这种情况。

有谁知道如何找到发生不匹配的子序列模式？

对于不匹配核函数，它允许 m 个不匹配。比如'tool'有3个3-gram（'too','ool'），错配核函数会统计'aoo','boo',...,'zoo','tao'...' tzo','toa'...'toz',....当m为1时。具体解释见http://www.cs.columbia.edu/~cleslie/cs4761/papers/string- kernel-slides.pdf 见第 12-17 页

如何编写一个可以计算该指标的 MATLAB 函数？

非常感谢。

使用 Python，我将如何返回一个加起来为 21 的正整数列表的子序列。

例如，对于列表：

子序列将是：

任何帮助，将不胜感激。

我有一个分类变量“世代”。我想使用 计算每一代最频繁的子序列TraMineR，但我不明白如何指定我需要某个群组。我已经尝试了我知道的所有可能的解决方案，但到目前为止没有任何效果。这是我无法指定的代码：

我正在寻找一个给出如下列表的算法：

[1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]

可以找到并返回给定值的所有子序列。例如，如果给定值 1，则函数将返回[[1, 1], [1, 1], [1, 1, 1, 1], [1]]。

我相信这类似于诸如总结数组的所有子序列或查找给定字符串的所有子序列之类的问题，但算法从来都不是我的强项。答案可以是伪代码或与语言无关。如果你不介意，你能解释一下解决方案的复杂性吗？

如果有帮助，我可以解释我需要这个做什么。如果你想要的话，请发表评论。

我需要找到将字符串转换为回文所需的最少插入次数。注意：插入可以发生在任何地方、末尾或内部。如果只是在最后，我们这里有个问题。

所以我发现这可以O(N**2)通过这个简单的技巧及时完成：

1. 设字符串为 s1。扭转它。让它成为s2。说长度是l。
2. 现在找到 s1 和 s2 的最长公共子序列。让它的长度为x。
3. 答案是l-x。

例如，假设s1 = abcda. 因此s2 = adcba。长度是 5。最长的公共子序列aba的长度是 3。所以插入的最小数量是5-3 = 2，这是实际的答案，结果是字符串 - 。adcbcda

但是，我无法理解其背后的逻辑。谁能向我解释它为什么有效？

而且，有没有O(N)可能的解决方案？

最近，我在一次采访中被问到以下问题。

给定一个字符串 S，我需要找到另一个字符串 S2，使得 S2 是 S 的子序列，S 也是 S2+reverse(S2) 的子序列。这里的“+”表示串联。对于给定的 S，我需要输出 S2 的最小可能长度。

有人告诉我这是一个动态编程问题，但是我无法解决它。有人可以帮我解决这个问题吗？

编辑-

有没有办法在 O(N ² ) 或更短的时间内做到这一点。

我有一个序列“abccabac”和一个子序列“abc”。我需要获取序列中所有出现的子序列“abc”的索引。什么是内存有效的方法？

例子：

输入：

输出：