Minimum Additions for Palindrome

Given a string s, determine the minimum number of characters that need to be appended to the end of s to transform it into a palindrome. A palindrome is a string that reads the same forwards and backwards.

The solution involves finding the longest suffix of s that matches a prefix of its reverse. Formally, let \( n \) be the length of s and let \( L \) be the length of the longest proper prefix of the combined string \( s#s^R \) (where \( s^R \) is the reverse of s). The answer is given by:

\( \text{result} = n - L \)

This can be efficiently computed using the failure function (LPS array) from the Knuth–Morris–Pratt (KMP) algorithm.

inputFormat

The input consists of a single line containing the string s. The string may contain letters, digits, or other characters.

outputFormat

Output a single integer representing the minimum number of characters that must be appended to the end of s to make it a palindrome.## sample

abcd

3