问题标签 [subsequence]

给定一个长度为 的数组n，要求编写程序来计算该给定数组的长度子序列的个数m。

下面是执行此操作的代码。请看一看。

现在，我的问题是：为什么seqLength每次减少的价值，以及这段代码究竟是如何工作的？

我正在研究一个最长的公共子序列程序，由于某种原因，即使我将其中的所有内容都初始化为 NULL，我的数组仍然被垃圾填满。

在我的 LongestCommonSubsequence 函数中，我做的第一件事是使用硬编码大小将二维数组初始化为 NULL。但是，在我初始化数组之后，它仍然充满了垃圾。所以当我点击我的 Traverse 函数时，没有一个 if 语句被命中，因为它从不等于那些字符。

这篇文章很好地解释了子序列的概念：生成子序列

但我不明白那个问题的答案，因为我是初学者。

我想知道的是我是否可以在不使用函数的情况下使我的 C 程序更高效，同时仍然保持简单易懂？

请注意，当我们将 NUM 定义为诸如 5111 或 100 之类的数字时，某些子序列会出现两次。有什么简单的方法可以解决这个问题吗？谢谢！

我在正在编写的一个不相关的程序中遇到了这个问题，我花了好几个小时试图解决它，因为我认为它会很有趣。是的，但我一直无法做到。我的代码只解决了一些子集的序列。这个问题也感觉像是一个一般的数学问题，几十年来可能已经以多种方式解决了，但我缺乏数学技能和术语来找到解决方案，或者在网上找到关于这个特定问题的任何东西。

我有一组子序列，我知道它们是更大的未知（超级？）序列的一部分。我不认为这些子序列是数学意义上的集合，因为它们是有序的，但它们的相似之处在于它们不包含重复的元素。master/super/whateversequence 也是如此。（为了清楚起见，我将其称为超序列。）

子序列都包含相同类型的数据，但是数据不是按字母顺序、升序或类似顺序排列的。从某种意义上说，数据是任意顺序的：在超序列中。这就是我感兴趣的。我想找到这些子序列的未知超序列。

为了简单起见，我尝试使用字母来解决这个问题，但我可以稍后重构代码以满足我的需要。显然，因为我仍在尝试解决这个问题，所以我首先为不包含重复元素的超序列想出了一个合适的词：FLOWCHARTS。

然后我想出了以下六个子序列：

这是我的顺序排序方法：

最后，我的代码找到了F,L,O,W,H,C,A,R,T,S这些子序列的超序列，它非常接近但并不完美。我还需要多次运行我的排序方法，所以我想出的“算法”也不完美。“规则映射”是一个哈希映射，其中键是字符对象的另一个哈希映射，它位于子序列中的键 Character 之后（因此在超序列中）。

是否有某种我可以使用的 Java 库来进行这种序列查找？有人可以在告诉我这叫什么和/或帮助我找到适合这项工作的算法方面指出我正确的方向吗？

此外，我的程序的缩短控制台输出：

我需要编写一个程序，例如，当给定数字 879 时，必须检查该数字是否为素数，以及它的所有数字子序列是否都是素数，意思是 87、79、8、7、9 等。到目前为止，我已经做了一个函数检查一个数字是否是素数，但不知道如何将一个数字拆分为其数字子序列。

n给定一个由字符组合组成的长度字符串A B D。

例一：AAAABAAAADADDDDADDDBBBBBBDDDDA

Threshold的x，给定的子串可以包含任何其他最大长度的连续子串x

Ex-2：对于AEx-1 中的子序列，AAAABAAAADA是阈值为 的具有 (1,11) 边界的合法子串x = 2。

同样，我想分别提取子字符串A和子字符串D，忽略B主字符串。主字符串中每种类型可以有许多子字符串。

模型输出：

A如果距离大于阈值会破坏字符串，我通过查找 s 之间的距离来实现一种效率低下的非算法方式。我不得不为A和单独运行这个D。这导致边界区域重叠。

我可以有更好的方法来解决这个问题吗？

编辑-1

合法子字符串可以是任意长度，但不应被大于 threshold 的其他子字符串污染x。这意味着在搜索它的子字符串时A，不应包含其他字符B或D连续大于阈值。

如果x = 2在搜索时A,AABBAAAA, AABDAAAA是有效的，但不是AADBDAAA, AABBBAAA。同样，在搜索 D（A并且B将成为污染者）时。

使用“Pham Trung”答案的 EDIT-2实施

代码：

输出：

代码无法在子字符串之后提取子1st字符串。

我不明白O(2^n)最长公共子序列算法的递归函数的复杂性。

通常，我可以将此表示法与算法的基本操作（在本例中为比较）的数量联系起来，但这一次在我看来没有意义。

例如，有两个长度相同的字符串5。在最坏的情况下，递归函数计算251比较。2^5甚至不接近那个值。

谁能解释这个函数的算法复杂性？

如何找到最长的重复（非重叠）子序列（不是子串）？

约束：

字符串 S 最多包含 100.000 个小写字符 'a'-'z'。

例子：

字符串hanadswomehanudsiome具有最长的重复（非重叠）子序列英俊。

预期的时间复杂度为 O(|S| log |S|) 或更好（|S| 是字符串 S 的长度）。

我正在尝试解决这个问题。问题是：给定一个字符串 S 和一个字符串 T，计算 S 中 T 的不同子序列的数量。

字符串的子序列是由原始字符串通过删除一些（可以是无）字符而不干扰剩余字符的相对位置而形成的新字符串。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

这是一个例子：S =“兔子”，T =“兔子”

答案应该是 3。

通过创建矩阵，我还知道动态编程解决方案。但是我想知道这种递归方法哪里出错了？目前它正在打印 6，但答案应该是 3。

我对 Java 和 Android Studio 有疑问；以下代码将成为退格按钮：

我正在尝试做一个退格按钮，我不知道这是否是制作这个的更好方法。所以，subSequence 方法返回我是一个字符序列，然后我放一个.toString()：

但它不起作用！该应用程序编译，但是当我按下退格按钮时，应用程序停止并且终端指出以下异常：

谢谢！