Editorial for IOI '00 P1 - Palindrome

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

A good method to solve this problem is to determine the length L of a longest common subsequence (maximal matching) for the input and its reverse. The answer then is N-L. An alternative approach is to match a prefix of the string with the reverse of a postfix.

The length of a longest common subsequence can be determined by dynamic programming. A triangular table can be constructed, of which only two rows need to be stored. The complexity is then \mathcal O(N) space and \mathcal O(N^2) time.

Note that constructing a witness (indicating where which characters have to be inserted to make a palindrome) is computationally more involved and is not asked.


There are no comments at the moment.