Taco: Shortest Palindrome Extension

Given a string s consisting of lowercase letters, your task is to determine the length of the shortest palindrome that can be obtained by appending characters to the end of s. In other words, you need to find the minimum length such that by concatenating an appropriate suffix to s, the resulting string becomes a palindrome.

For example:

• For s = "abac", the shortest palindrome has length 5.
• For s = "abcd", the answer is 7.
• For s = "race", the answer is 7.
• For s = "level", it is already a palindrome, so the answer is 5.
• For s = "aa", the answer is 2.
• For s = "a", the answer is 1.

Note: The solution should use the approach of checking the longest palindromic prefix of s and then calculating the additional characters needed. The palindrome condition should be based on the standard definition where a string reads the same forward and backward. All formulas or mathematical expressions must be provided in LaTeX format when necessary.

For instance, if you let \(n\) denote the length of s and \(k\) be the largest index such that the prefix \(s[0\ldots k]\) is a palindrome, then the answer is computed as:

[ \text{answer} = n + (n - (k+1)) ]

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

outputFormat

Output a single integer representing the length of the shortest palindrome that can be formed by appending characters to the end of s.

## sample

abac

5