← 返回题目列表

AtCoder · code_festival_2017_qualc_c

C. 插入“x”

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个字符串 s 由小写英文字母组成。 Snuke可以重复执行以下操作:

  • 插入一封信 x 到任意位置 s 他选择的,包括开头和结尾 s.

Snuke 的目标是转向 s 变成回文。 确定目标是否可以实现。如果可以实现,找出所需的最少操作数。

注释

A 回文 是一个字符串,向前和向后读取相同。 例如, 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 → xxxxxxx