10453 - Make Palindrome
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.
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.
abcd aaaa abc aab abababaabababa pqrsabcdpqrs aaab acaaaba zzzaaazz pooq aoob azbzczdzez
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