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
我尝试查看原始最长公共子序列问题，但它用于比较两个序列以找到最长公共子序列….但这里只有一个序列，我们必须从中找到子序列。请让我知道解决此问题的最佳方法是什么，以找到最佳解决方案。
实际上这是应用于序列的最长公共子串问题及其逆：http://en.wikipedia.org/wiki/Longest_common_substring_problem
这与最长公共子序列不同：http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence
将最长公共子字符串应用于字符串及其反向。
|
1
|
LCS ("abcdefgedcg","gcdegfedcba") ="cde"
|
编辑：不是土豆瓦特指出的子序列，不是子序列。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/269277.html