ACM-ICPC-OJ训练营

问题 3429 --完美回文

3429: 完美回文

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 5
[提交][状态][讨论版][命题人:]

题目描述

给定长度为n的字符串S=s0s1…sn-1，令f(S,d)表示将S左移d次后获得的字符串。也就是说f(S,d)=s(d+0)modn s(d+1)modn … s(d+n-1)modn。若S为完美回文，则对于所有非负整数d，f(S,d)都是回文串。
给定长度为n的仅由小写英文字母组成的字符串A=a0a1…an-1，您可以对A进行任意次以下操作（包括零次）：选择整数i满足0≤i＜n并将ai改为任何小写英文字母。
求将A变为完美回文的最少操作次数。
称长度为n的字符串P=p0p1…pn-1是回文串，若对于所有0≤i＜n有pi=pn-1-i。

输入描述

有多组测试数据。第一行输入一个整数T表示测试数据组数，对于每组测试数据：
第一行输入一个仅由小写英文字母构成的字符串a0a1…an-1(1≤n≤105)。
保证所有数据中字符串长度之和不超出106。

输出描述

每组数据输出一行一个整数表示将A变为完美回文的最少操作次数。

样例输入

2
abcb
xxx

样例输出

2
0

提示

对于第一组样例数据，可以将第一和第三个字符变为'b'，这样字符串将变为"bbb"。容易发现对于所有非负整数d，f("bbb",d)="bbb”且“bbb”是回文串，因此“bbb”是完美回文。这些变化需要消耗2次操作，可以证明这是最少需要的操作次数。

对于第二组样例数据，“xxx”已经是完美回文，因此无需任何操作。

2022 ICPC 区域赛南京站 A题

来源

23软4杨宗奇

[提交][状态]