Как найти самую длинную непрерывную подпоследовательность, обратная сторона которой также является подпоследовательностью

Question

Предположим, у меня есть последовательность x1, x2, x3 ..... xn, и я хочу найти самую длинную непрерывную подпоследовательность xi, xi + 1, xi + 2 ...... xi + k, обратная сторона которой также является подпоследовательностью данной последовательности. И если есть несколько таких подпоследовательностей, то я также должен найти наименьшее я.

например: - рассмотрим последовательности:

abcdefgedcg здесь я = 3 и к = 2

aabcdddd здесь i = 5, k = 3

Я попытался посмотреть исходную самую длинную общую проблему подпоследовательности, но она используется для сравнения двух последовательностей, чтобы найти самую длинную общую подпоследовательность .... но здесь есть только одна последовательность, из которой мы должны найти подпоследовательности. Пожалуйста, дайте мне знать, как лучше всего подойти к этой проблеме, чтобы найти оптимальное решение.

Answer 1

На самом деле это самая длинная общая проблема с подпунктами string , применяемая к последовательности и ее обратной последовательности: http://en.wikipedia.org/wiki/Longest_common_substring_problem

Это отличается от самой длинной общей подпоследовательности последовательности : http://en.wikipedia.org/wiki/Subsequence#Substring_vs._subsequence

Answer 2

применить самую длинную общую подстроку к строке и наоборот.

 LCS ("abcdefgedcg", "gcdegfedcba") = "cde"

РЕДАКТИРОВАТЬ : не подпоследовательность, как указывает калифорнийская вода, не подпоследовательность.