/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
英小文字のみからなる文字列 s があります。 すぬけ君は、次の操作を繰り返し行うことができます。
- s の任意の位置 (先頭および末尾を含む) をひとつ選び、英小文字
xをひとつ挿入する。
すぬけ君の目標は、s を回文にすることです。 すぬけ君の目標が達成可能か判定し、達成可能ならば必要な操作回数の最小値を求めてください。
注釈
回文とは、前後を反転しても変わらない文字列のことです。
例えば、a, aa, abba, abcba は回文ですが、ab, abab, abcda は回文ではありません。
制約
- 1 \leq |s| \leq 10^5
- s は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
s
出力
すぬけ君の目標が達成可能ならば、必要な操作回数の最小値を出力せよ。
達成不可能ならば、代わりに -1 を出力せよ。
入力例 1
xabxa
出力例 1
2
例えば、次のように操作を行えばよいです (新しく挿入された x は太字で表されています)。
xabxa → xaxbxa → xaxbxax
入力例 2
ab
出力例 2
-1
どのように操作を行っても、s を回文にできません。
入力例 3
a
出力例 3
0
s は最初から回文です。
入力例 4
oxxx
出力例 4
3
例えば、次のように操作を行えばよいです。
oxxx → xoxxx → xxoxxx → xxxoxxx
Score : 400 points
Problem Statement
We have a string s consisting of lowercase English letters. Snuke can perform the following operation repeatedly:
- Insert a letter
xto any position in s of his choice, including the beginning and end of s.
Snuke's objective is to turn s into a palindrome. Determine whether the objective is achievable. If it is achievable, find the minimum number of operations required.
Notes
A palindrome is a string that reads the same forward and backward.
For example, a, aa, abba and abcba are palindromes, while ab, abab and abcda are not.
Constraints
- 1 \leq |s| \leq 10^5
- s consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
Output
If the objective is achievable, print the number of operations required.
If it is not, print -1 instead.
Sample Input 1
xabxa
Sample Output 1
2
One solution is as follows (newly inserted x are shown in bold):
xabxa → xaxbxa → xaxbxax
Sample Input 2
ab
Sample Output 2
-1
No sequence of operations can turn s into a palindrome.
Sample Input 3
a
Sample Output 3
0
s is a palindrome already at the beginning.
Sample Input 4
oxxx
Sample Output 4
3
One solution is as follows:
oxxx → xoxxx → xxoxxx → xxxoxxx