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

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

Это вариант на Longest common substring problem. Вы ищете самую длинную общую подстроку вашего ввода и ее обратную сторону.

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

Answer 2

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

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

Answer 3

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

Answer 4

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