问题标签 [subsequence]

我们必须找到包含另一个字符串的一些字谜作为子序列的字符串的子字符串的数量。

仅当开始或结束位置不同时，子字符串才被认为是不同的。

我认为这个问题是“字符串中子序列的出现次数”和“在包含另一个字符串的所有字符的字符串中查找最小窗口”的应用之一。

但即使在组合代码中进行了多次更改后，我也无法提出解决方案。粘贴我的代码是没有用的，因为我知道我错了。我想知道的是我们如何在没有暴力解决方案的情况下有效地解决这个问题。

代码 ：

此代码为上述问题提供输出=3。我知道一旦到达第一个字符串的末尾，我就无法检查其中的每个子字符串。

除了指数时间复杂度的蛮力检查每个可能的子字符串之外，还有其他方法吗？

我有以下算法，它返回数组中最大子序列的总和。最大的和在数组的左半部分、右半部分或中间（分而治之）......如果它通过中间，我可以返回索引。但是如果子序列在数组的左半部分或右半部分，我无法弄清楚它们会是什么（递归有点混乱）。如果需要，我可以在方法之外定义索引的变量。这是方法：

给定一个正数数组，您需要找到两个不相交的子序列，其最小差小于或等于 n。这些子序列可能是连续的，也可能不是连续的

我认为这可以使用 DP 来完成，但我无法得出递归。

编辑：对于那些投反对票的人：我非常清楚我不想要代码并且我自己已经尝试过。我所寻找的只是对产生样本结果的数学过程的解释。

第一个问题。我做了很多研究，最后求助于提问，所以如果我在某个地方错过了答案，我深表歉意。我有一个问题我真的很挣扎：

编写一个接受三个命令行参数的 Python 3 脚本：

1. 包含 n 个由空格分隔的字符串的文本文件的名称。
2.一个正整数k。
3. 脚本将创建的文本文件的名称，以便存储来自输入文件的 n 个字符串中的 k 个唯一字符串的所有可能子序列，每行一个子序列。

例如，假设命令行是 gen.py input.txt 3 output.txt 并且文件 input.txt 包含以下行：

Python Java C++ Java Java Python

那么程序应该创建包含以下行的文件 output.txt (以任何顺序）：

Python Java C++
Python C++ Java
Java C++ Python
C++ Java Python

这些组合应该通过您的生成器函数实现生成（即使用关键字yield）。

据我了解，根据示例输出，这并不完全符合子序列的定义；它们也不是很排列，所以我不知道如何去做。我知道如何处理文件 IO 和命令行参数部分，我只是无法获得正确的子序列。我不需要直接的答案，因为我应该解决这个问题，但如果有人能给我一些有用的见解，我将不胜感激。

问题：给定一个整数数组 A[]，长度 = n 和一个给定的整数值 TARGET。找到满足其总和小于 TARGET 且最接近该 TARGET 的子序列（可能不连续）。

例如：A[] = [10, -2, 3, 7]。目标 = 14。答案 = {10, 3}

我在 Hackerrank 挑战中遇到了这个问题，我无法找出任何多项式时间解决方案，它首先听起来对一些动态规划问题很熟悉，但在这种情况下，条件“不大于”和“最近”似乎消除了该解决方案。

从我遵循动态规划方法的第一个想法开始，在 i-problem (i=0->n-1) 处，我们需要评估所有包含 A[i] 或不包含 A[i] 的子序列，后者被称为 S[i-1]，所以只关注以 A[i] 作为最后一个元素的所有子序列。

我们不能仅仅依赖以前解决的问题（0-> i-1），因为我们需要的总和必须小于并且最接近目标可能不会从较小的解决方案中产生，它可能是从第二个解决方案产生的，第三个加上最后一个元素 A[i]，并且遍历所有包含 A[i] 的子序列将需要遍历所有 2^i - 1 个子集，不包括单个集合 {A[i]}。

对这类问题有什么建议吗？

我正在尝试合并多个序列，如下例所示：

给定的序列是相同的无重复序列（未给出）的所有子序列。如果无法确定顺序 - 就像示例中的'four'和一样'five'，也可以颠倒 - 任何一种解决方案都可以。

这个问题类似于多序列比对，但我怀疑有一个（算法上）更简单的解决方案，因为它受到更多限制（没有重复，没有交叉边缘）。例如。当从所有元素的并集开始时，我只需要对元素进行排序——但我似乎找不到一种体面的方法来从输入序列中推断出潜在的顺序。

该示例是在 Python 中的，并且期望的解决方案也是，但问题具有一般算法性质。

想象一下，我们有一个列表，比如 [255,7,0,0,255,7,0,0,255,7,0,0,255,7,0,0] 我们想找到包含子序列中所有项目的最短公共子序列（NOT SUBSTRING），255,7,0,0在这种情况下，我们不知道模式的长度。

即使中间有一些像这个序列这样的乱码，该程序也应该可以工作。255,7,0,0,4,3,255,5,6,7,0,0,255,7,0,0,255,7,0,1,2,0，它应该返回重复的子序列255,7,0,0。

我尝试了最长的公共子序列，但由于算法是贪婪的，它不适用于这种情况，因为它会返回所有匹配而不是最短的匹配。非常感谢您的帮助。

我被困在做大学作业。任务是找到一种递归然后动态编程的方法来计算数组的最长、后继、升序子序列的长度。例如，如果数组是： {4 , -5 , -3, -2, 5, -2, 0, 3 , 2} 最大长度将是 4 子序列 {-5, -3, -2, 5 }。我很难找到递归方式，如果没有递归方式，就不可能为我找到动态方式。
我尝试过编程，但我知道这是错误的，我不知道如何修复它：

我试图在 Java 中解决的问题需要将输入数组划分为所有允许的子序列，其中允许的子序列仅包含连续值。例如，我希望 {A,E,D} 返回 {A,E,D},{A,E},{A},{E,D},{D},{E}

这与这个问题的不同之处在于（对于上面的例子）
1）我有“连续值”规则，这意味着 {A,D} 是不允许的，
2）我不能依赖此处答案中的 Python 语法。

我的问题尤其是如何对更一般的子序列问题实施“连续值”规则。

到目前为止，我已经为示例 {1,2,3} 提出了一种算法：
1. 复制 {1,2,3} 并存储在arr
2. 将 {1,2,3} 附加到解决方案中，剥离 3
3. 将 {1,2} 附加到解决方案，剥离 2
4. 将 {1} 附加到解决方案。从arr
5 中删除 1。将 {2,3} 附加到解决方案剥离 3
6.将 {2} 附加到解决方案。从arr
7 中删除 2。将 {3} 附加到解决方案

我希望从第一个元素开始提取向量的增加子序列。例如，从这个向量：
a = c(2, 5, 4, 0, 1, 6, 8, 7)

...我想返回：
res = c(2, 5, 6, 8)。

我以为我可以使用循环，但我想避免它。另一个尝试sort：

基本上我对输入向量进行排序并检查索引是否验证了“右侧没有索引较低”的条件，这意味着事先没有更大的值。

但这似乎有点复杂，我想知道是否有更简单/更快的解决方案，或者 R 中的预构建函数。

谢谢