How to find the longest continuous subsequence whose reverse is also a subsequence
假设我有一个序列x1,x2,x3…..xn，我想找到最长的连续子序列xi,xi 1,xi 2……xi k，它的逆也是a给定序列的子序列。
如果有多个这样的子序列，那么我还必须找到最小的 i.
ex:- 考虑序列：
abcdefgedcg
这里 i=3 和 k=2
aabcdddd
这里 i=5, k=3
我尝试查看原始最长公共子序列问题，但它用于比较两个序列以找到最长公共子序列….但这里只有一个序列，我们必须从中找到子序列。请让我知道解决此问题的最佳方法是什么，以找到最佳解决方案。
- 对于第一个示例，我得到 i=2 k=3，对于第二个示例，我得到 i=5 k=4。
- @Potatoswatter：不，你没有。再次阅读问题的陈述。 “k” 的定义搞砸了。 k 是子串的长度减一，i 是从一开始的索引。您假设 k 是子字符串的长度，而 i 是与开头的距离，但这不是它们的定义方式。
- @Eric：那好吧。虽然这行得通，因为他保证为任何非空输入找到一个子字符串，但仍然建议 OP 他使用正常的编程约定。
- 嘟嘟？ stackoverflow.com/questions/2463364/…
实际上这是应用于序列的最长公共子串问题及其逆：http://en.wikipedia.org/wiki/Longest_common_substring_problem
这与最长公共子序列不同：http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence
- @Potatoswatter：最长的公共子串问题比较两个字符串以找到公共子串……我们如何将相同的原理应用于单个序列及其反向？请解释。
- @iecut：将序列视为字符串，将其反向视为另一个字符串。将算法应用于这两个字符串。您可以向后迭代序列以获得第二个字符串。
- @Potatoswatter 它不是最长的公共子串，因为他要求 subsequence ，所以我们可以应用 LCS(只是改变比较)它变成 MCS(最小公共子序列)，根据关于字符串和反转字符串的问题
将最长公共子字符串应用于字符串及其反向。
|
1
|
LCS (“abcdefgedcg”,“gcdegfedcba”) =“cde”
|
编辑：不是土豆瓦特指出的子序列，不是子序列。
来源：https://www.codenong.com/2475040/
