题目描述

回文串就是类似aba, bcdcb,AAA这样的字符串。即将它反转过来，与原串相等。

另外这样的字符串，例如ab，我们可以发现，在最后补充一个a也能使它变成一个回文串 aba，或者在他的最前面插入一个b，能使它变成一个回文串bab

现在输入一个字符串（它很可能不是回文串），那么问最少给它插入多少个字符，能使它变成一个回文串?

输入格式

一行，一个字符串

*字符串可能出现类似%、等字符，保证均为可见字符。

输出格式

一个数字，需要添加的最少字符数

如果不需要添加字符，输出0

样例

####样例输入

ab

####样例输出

1

数据范围与提示

2 <= 字符串长度 <= 200

保证输入的字符串中间不会出现空格

####提示 把输入的字符串反转过来，与原串求LCS（最长公共子序列），然后.................................

####其它 感谢sxy同学贡献题目。