## 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 of a longest common subsequence (maximal matching) for the input and its reverse. The answer then is . 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 space and 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