题目链接：SHOI2011]双倍回文 - 洛谷

前置知识：回文自动机

有关回文自动机的介绍以及求法，这里推荐三篇博客

回文树 - OI Wiki

回文自动机学习笔记 - bztMinamoto - 博客园 (cnblogs.com)

Manacher 回文自动机学习笔记_Clove_unique的博客-CSDN博客_回文自动机

这几个博客都讲解得很好，结合起来食用效果更佳！

如果觉得太抽象的话，可以在纸上画几个回文自动机，理解每个操作的原理。

题意

一个长度为$n$的字符串$S$，在$S$的子串中寻找形如$ss$（$s$为回文串）的最长$ss$长度

思路

首先建立回文自动机，在求$fail$指针时，我们维护一个$go$指针，指向长度不大于当前回文串一半的最长回文后缀的节点。

我们考虑每次插入字符$c$的过程。

当我们新建一个节点$x$时，若该节点的父节点的长度已经小于等于该节点长度的一半，我们直接让$go_x $指向父节点，即$fail_x$。

否则我们从$x$的父节点的$go$指针不断向上跳，直到当前节点两端能拓展字符$c$并且拓展后长度不大于$x$的长度，那么$go_x$指向当前节点的儿子为$c$的子节点。

现在我们枚举回文自动机上的每个节点，若当前节点的长度为$4$的倍数且它的$go$指针指向的节点长度刚好为当前节点长度的一半，那么我们对该长度取$\max$，最后输出$\max$即可。

代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

struct Palindromic_Automaton {
    int s[N], top; // 原串
    int ch[N][26], fail[N], len[N], tot, last;

    Palindromic_Automaton() {
        s[0] = -114514;
        tot = -1;
        New(0); // 偶根
        New(-1); // 奇根
        fail[0] = 1;
        last = 0;
    }

    int New(int length) {
        len[++ tot] = length;
        return tot;
    }

    int Get_Fail(int x) { // 找最长的回文后缀
        while (s[top - len[x] - 1] != s[top]) {
            x = fail[x];
        }
        return x;
    }
    int go[N];
    void Extend(int c) {
        s[++ top] = c;
        int now = Get_Fail(last);
        if (!ch[now][c]) {
            int x = New(len[now] + 2);
            fail[x] = ch[Get_Fail(fail[now])][c];
            ch[now][c] = x;
            if (len[fail[x]] <= len[x] / 2) {
                go[x] = fail[x];
            } else {
                int y = go[now];
                while (len[y] + 2 > len[x] / 2 || s[top - len[y] - 1] != s[top]) {
                    y = fail[y];
                }
                go[x] = ch[y][c];
            }
        }
        last = ch[now][c];
    }
    void solve() {
        int ans = 0;
        for (int i = 2; i <= tot; ++ i) {
            if (len[i] % 4 == 0 && len[i] == len[go[i]] * 2) {
                ans = max(ans, len[i]);
            }
        }
        cout << ans << '\n';
    }
} pam;
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    string s;
    cin >> n >> s;
    for (const auto &x : s) {
        pam.Extend(x - 'a');
    }
    pam.solve();
    return 0;
}

前置知识： 回文自动机

题意

思路

代码

前置知识：回文自动机