# UVa 10453

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