Подстрока и ее оборот в строке

Question

Мой профессор говорил об этом в классе динамического программирования и попросил нас подумать над этим. Она также дала нам несколько примеров. Учитывая строку, мы должны были найти самую длинную непрерывную подпоследовательность, обратная сторона которой также является подпоследовательностью, присутствующей в данной строке.

Пример:

INPUT: pqrstuvtsrv
OUTPUT: i=3, k=2

rst -> tsr (rst found first at i=3 and for 2 more positions)

INPUT: mpqrsrqp
OUTPUT: i=2, k=6
pqrsrqp in reverse

INPUT: mmpqssss
OUTPUT: i=5, k=3

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

Answer 1

Это вариант самой длинной общей подстроки 1002 *. Вы ищете самую длинную общую подстроку вашего ввода и ее обратную.

Может быть более простое решение для этого конкретного случая, но на данный момент я сомневаюсь в этом. =)

Answer 2

Это не работает, потому что вы также должны следить за совпадением. Если вы используете LCS, вы также найдете палиндромы, у которых может быть или не быть обратный в исходной строке.

Answer 3

То, что вы ищете, называется Самая длинная палиндромная подстрока и имеет известные решения с линейным временем. Надеюсь, я помог.

Answer 4

Похоже на задание для дерева суффиксов (на самом деле два или обобщенное дерево суффиксов для них обоих). Но это класс динамического программирования, а не класс структур данных, возможно, нет.

Если вам нужен полный спойлер, найдите «самая длинная распространенная проблема с подстрокой». Но я бы посоветовал вам не смотреть слишком внимательно на все, что кажется решением. Одна из проблем с подсказками для задач динамического программирования заключается в том, что решение часто опирается на одно очень умное наблюдение, и вы либо получаете его, либо нет.