c++# 完美回文 ## 题目描述 给定长度为$n$的字符串 $S=S_0S_1···S_{n-1}$ ，令 $f(S,d)$ 表示将 $S$ 左移 $d$ 次后获得的字符串。也就是说 $f(S,d)=S_{(d+0) mod (n)}S_{(d+1) mod (n)}···S_{(d+n-1) mod (n)}$ 。 称 $S$ 为完美回文，若对于**所有**非负整数 $d$ , $f(S,d)$ 都是回文串。 给定长度为 $n$ 的仅由小写英文字母组成的字符串 $A = a_0a_1 · ·

首先，您的问题是关于算法竞赛的题目，不属于自然语言处理范畴，但我会尽力回答。

这道题目可以通过 Manacher 算法来解决。算法的基本思路是，对于每个位置 $i$，求出以 $i$ 为中心的最长回文半径 $p_i$。具体实现可以参考以下步骤：

1. 预处理字符串，将每个相邻的字符之间插入一个分隔符，得到一个新的字符串 $S'$。例如，对于字符串 $ABCD$，插入分隔符后变为 $A#B#C#D$。

2. 维护两个变量 $maxRight$ 和 $center$，分别表示已知的所有回文串中最右侧的位置和其中最右侧的回文串的中心。同时，维护一个数组 $p$，表示以每个位置为中心的最长回文半径。

3. 从左到右遍历字符串 $S'$，对于每个位置 $i$，计算 $p_i$ 的值。如果 $i$ 在最右侧的回文串内部，可以利用已知的信息快速计算 $p_i$ 的值；否则，暴力枚举计算。

4. 在计算 $p_i$ 的过程中，如果当前回文串的右侧位置超过了 $maxRight$，则更新 $maxRight$ 和 $center$。

5. 最终的答案是 $n - \max\{p_i\}$，其中 $n$ 是字符串的长度。

具体实现可以参考以下代码（仅供参考，可能存在错误或不足）：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100005;

char s[MAXN], s_new[MAXN * 2];
int p[MAXN * 2], maxRight, center;

int main() {
    cin >> s;
    int n = strlen(s);
    // 预处理字符串
    for (int i = 0; i < n; i++) {
        s_new[i * 2] = '#';
        s_new[i * 2 + 1] = s[i];
    }
    s_new[n * 2] = '#';
    // 求解最长回文半径
    int ans = 0;
    for (int i = 0; i < n * 2 + 1; i++) {
        if (i < maxRight) {
            p[i] = min(p[2 * center - i], maxRight - i);
        } else {
            p[i] = 1;
        }
        while (i - p[i] >= 0 && i + p[i] < n * 2 + 1 && s_new[i - p[i]] == s_new[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] - 1 > maxRight) {
            maxRight = i + p[i] - 1;
            center = i;
        }
        if (i % 2 == 0) {
            ans += p[i] / 2;
        } else {
            ans += (p[i] + 1) / 2;
        }
    }
    cout << n - ans << endl;
    return 0;
}