Editorial for IOI '00 P1 - Palindrome - Olympiads Online Judge

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$ $L$ of a longest common subsequence (maximal matching) for the input and its reverse. The answer then is $N-L$ $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)$ $O (N)$ space and $\mathcal O(N^2)$ $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.

Comments

There are no comments at the moment.