问题标签 [subsequence]

String.subSequence()有以下javadoc：

返回一个新的字符序列，它是该序列的子序列。

调用表单的这个方法

行为方式与调用完全相同

定义此方法以便 String 类可以实现 CharSequence 接口。

谁能解释一下？

我的程序应该根据用户的输入生成字母模式。我必须使用递归将每个输出设置为不同的。我已经这样做了。接下来我必须用另一种方法比较两个输出，并使用递归来找到两者之间最长的公共子序列的长度。问题是我不知道如何比较它们。由于它们是无效的结果，我不知道如何将它们转换为字符串。

}//鳍。

有没有办法检查一个字符串是否是 Prolog 中另一个字符串的子字符串？我尝试将字符串转换为字符列表，然后检查第一组是否是第二组的子集，这似乎不够严格。这是我当前的代码：

如果我用

isSubstring("test","tesZting")。

它返回是，但应该返回否。

从https://codegolf.stackexchange.com/questions/5529/is-string-xa-subsequence-of-string-y复制的问题

T 给定字符串 X 和 Y，判断 X 是否是 Y 的子序列。空字符串被认为是每个字符串的子序列。（例如，'' 和 'anna' 是 'banana' 的子序列。）

他们的任何功能是否已经在 J​​ava 或一些通用库中？

输入

X，一个可能为空的区分大小写的字母数字字符串 Y，一个可能为空的区分大小写的字母数字字符串 输出

True 或 False（或等效项），正确指示 X 是否是 Y 的子序列。 I/O 示例

• '' 'z00' 真
• 'z00' 'z00' 真
• 'z00' '00z0' 假
• 'aa' '安娜' 真
• '安娜' '香蕉' 真
• '安娜' '香蕉' 错误

假设我有一个列表，x=[1, 2, 3, 4]它包含子列表[1]、[2]、[3]、[4]、[1, 2]、[2, 3]、[3, 4]、[1,2,3]和。但它不包含类似的东西，因为在 x 中 2 出现在 1 和 3 之间时存在间隙。[2,3,4][1,2,3,4][1, 3]

有谁知道最好的方法是测试一个列表是否包含在另一个列表中而没有间隙？我曾想过一个 for-loop 解决方案，但它可能不是一个很好的解决方案。谢谢。

确定性自动机查找字符串中的子序列数？如何构造 DFA 以查找出现字符串的数量作为另一个字符串中的子序列？

例如。在 "ssstttrrriiinnngggg" 中，我们有 3 个形成字符串 "string" 的子序列？

同样要找到和要搜索的字符串都只包含来自特定字符集的字符。我有一些关于将字符存储在堆栈中的想法，相应地弹出它们直到我们匹配，如果不匹配再次推送。请告诉 DFA 解决方案？

我用 C++ 编写了一个函数，它执行以下操作：给定一个（可能很长的）向量x和一个阈值，thr找到、和≥y的子序列。目的是找到“看起来相同”的位置的短子序列，即图形的分辨率为。xx[1]∈yx[length(x)]∈y∀i∈1:length(y) y[i+1]-y[i]thrxplot(x)plot(x[subsequence])thr

该函数是 R 包的一部分，使用该Rcpp接口调用 C++ 函数。来源在这里： https ://gist.github.com/kenahoo/8922376 。（它实际上对 a 进行操作data.frame，而不是简单的向量，但它相当于将每一列作为向量独立地操作，然后合并索引序列。）

我想找到一个等效的纯 R 解决方案，它既好又高效 - 一个明显的想法是类似的which(diff(x)>thr)，但这不合适，因为它会错过任何缓慢漂移的值，这些值随着时间的推移而超过thr.

例子：

这会产生这样的近似值：

欢迎对此提出任何想法。

我想知道实现这一点的最佳方法是什么。

想不出一个好方法来保存需要保存的信息，例如索引和值的数量，最后是重复的实际数量

我的未排序数组是

在这个数组10,22,33,50,60,80中，按升序排列，所以输出必须是6。

一般来说，我想要由数组元素组成的升序列表的最长可能长度，并从第一个元素开始。

我试过这个：

但没有成功。

我正在练习算法，我的任务之一是计算给定0 < n <= 10^6数字的所有最长递增子序列的数量。解决方案O(n^2)不是一个选项。

我已经实现了查找 LIS 及其长度（LIS 算法），但该算法将数字切换到尽可能低的值。因此，不可能确定具有先前数字（较大的数字）的子序列是否能够达到最长的长度，否则我猜我可以只计算那些开关。

关于O(nlogn)的任何想法？我知道应该使用动态编程来解决它。

我实现了一个解决方案，它运行良好，但它需要两个嵌套循环(i in 1..n) x (j in 1..i-1)。
所以我认为它是O(n^2)，但它太慢了。

我什至尝试将这些数字从数组移动到二叉树（因为在每次i迭代中，我都会查找所有较小的数字然后number[i] - 遍历元素i-1..1），但它甚至更慢。

示例测试：