Shortest Palindrome Extension

Given a string s consisting only of the characters 'a', 'b', and 'c', determine the length of the shortest palindrome that can be formed by appending characters to the end of s.

Formally, for a string \(s\) of length \(n\), find the minimum integer \(L\) such that there exists a string \(x\) (possibly empty) with
\(P = s+x\) being a palindrome and \(L = n + |x|\). In other words, if you can find a smallest index \(i\) (0-based) such that the substring \(s[i]\) to \(s[n-1]\) is a palindrome, then the answer is \(n+i\).

For example, given s = "abca", since "bca" is not a palindrome but "ca" is not, and only "a" is, the answer equals \(4+3=7\).

inputFormat

The input consists of a single line containing a non-empty string s which only contains the characters 'a', 'b', and 'c'.

You will read the input from standard input (stdin).

outputFormat

Print one integer representing the length of the shortest palindrome that can be formed by appending characters to the end of s.

The output should be written to standard output (stdout).

abca

7