正经题解｜国王的魔镜

【算法分析】

最终的字符串是通过字符串变换而来，使用递归去寻找这个串。在递归的过程中反转后半部分的串，如果不相同则已经找到。由于左半部分是右半部分的镜像，因此答案是一样的，只需要递归左半部分就可以。

【参考代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;
char s[maxn];
int ans;
void dfs(int l, int r) {
    int mid = (l + r) >> 1;
    string left(s + l, s + mid + 1),right(s+mid****+r+1);
    reverse(right.begin(), right.end());
    if (left != right) {
        cout << r - l + 1;
        return;
    }
    dfs(l, mid);

}
int main() {
    cin >> s + 1;
    dfs(1, strlen(s + 1));
    return 0;
}

【时间复杂度】

$O(nlogn)$

【预计得分】

$100pts$