解题思路

要把一个长度为偶数的字符串变为“重复字符串”（前半段与后半段完全相同），最少需要修改多少次？ 设字符串长度为 n，前半段为 s[0..n/2-1]，后半段为 s[n/2..n-1]。要使两半相等，只需逐位比较这两个长度为 n/2 的子串，在每一对对应位置 (i, i+n/2) 上：

• 若字符已相同，则无需修改；
• 若字符不同，则至少需要 1 次修改（把其中任意一个改成另一个即可）。

因此，答案就是两半对应位置的“汉明距离”（不同位置的个数）。

题目内容

我们定义一个长度为偶数字符串为重复字符串，当且仅当该字符串的前半段等于后半段。

例如 "$aaaa$"、"$abhabh$" 是重复字符串。

小红拿到了一个字符串，她每次操作可以选择一个字符，将其修改为任意一个字符。

小红想知道，她最少多少次操作后，可以把该字符串变成重复字符串?

输入描述

一个长度为偶数的字符串。长度不超过 $10^5$ 。

输出描述

将其变成重复字符串的最小操作次数。

样例1

输入

abhabh

输出

0

说明

$abhabh$ 本身就是重复字符串，不再需要操作

样例2

输入

abagba

输出

1

说明

将第一个字符改成 '$g$' 即可。