UVa 10453
From Algorithmist
Contents |
[edit] 10453 - Make Palindrome
[edit] Summary
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.
[edit] Explanation
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.
[edit] Input
abcd aaaa abc aab abababaabababa pqrsabcdpqrs aaab acaaaba zzzaaazz pooq aoob azbzczdzez
[edit] Output
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
