UVa 10453

From Algorithmist
Jump to navigation Jump to search

10453 - Make Palindrome[edit]

Summary[edit]

The idea is that to make the shortest palindrome, calculate the longest common subsequence of the string and its reverse - this will give you the optimal overlap in the palindrome. The rest can be added on.

Explanation[edit]

In the worst case, just insert everything in the back - this will give you a palindrome. How can we do better? Since we would do this inserting in (reverse) order, but anywhere in the string, we just need to find use the longest common subsequence - these overlaps are the cost that we're saving. The rest can be inserted in order in accordance to these overlaps.

Input[edit]

abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs

aaab
acaaaba
zzzaaazz
pooq
aoob
azbzczdzez

Output[edit]

3 abcdcba
0 aaaa
2 abcba
1 baab
0 abababaabababa
9 pqrsabcdpqrqpdcbasrqp
0
1 baaab
2 acbaaabca
1 zzzaaazzz
2 pqooqp
2 abooba
5 azbzcezdzeczbza