Shortest Palindrome Length by Appending Characters

Given a string s, your task is to determine the length of the shortest palindrome that can be formed by appending characters to the end of the string.

The final palindrome is constructed as s + X, where X is chosen to be as short as possible such that the resulting string is a palindrome. In other words, find the minimum non-negative integer i such that the substring s[i:] is a palindrome. Then, if n is the length of s, the length of the shortest palindrome is given by:

$$ n + i $$

For example, if s = "abab", we observe that s[1:] = "bab" is a palindrome. Hence, by appending the reverse of s[0:1] to s (i.e. "a"), we obtain "abab" + "a" = "ababa" which is a palindrome of length 5.

inputFormat

The input consists of a single line containing the string s.

outputFormat

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

abab

5