跳转至

回文自动机

代码修改自 ©OI wiki。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 4e3 + 9;
int sz, tot, last;
int cnt[MAXn], ch[MAXn][128], len[MAXn], fail[MAXn];
char s[MAXn], d[MAXn];

// 建立一个新节点，长度为 l
int node(int l) {
    sz ++;
    memset(ch[sz], 0, sizeof(ch[sz]));
    len[sz] = l;
    fail[sz] = cnt[sz] = 0;
    return sz;
}

// 初始化
void clear() {
    sz = -1;
    last = 0;
    s[tot = 0] = '$';
    node(0);
    node(-1);
    fail[0] = 1;
}

// 找后缀回文
int getfail(int x) {
    while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
    return x;
}

// 建树
void insert(char c) {
    s[++tot] = c;
    int now = getfail(last);
    if(!ch[now][c - 'a']) {
        int x = node(len[now] + 2);
        fail[x] = ch[getfail(fail[now])][c - 'a'];
        ch[now][c - 'a'] = x;
    }
    last = ch[now][c - 'a'];
    cnt[last] ++;
}

lli solve() {
    lli ans = 0;
    for(int i = sz; i >= 0; i--)
        cnt[fail[i]] += cnt[i];
    for(int i = 1; i <= sz; i++)
        ans = max(ans, 1ll * len[i]);
    return ans;
}

int main() {
    clear();
    scanf("%s", d + 1);
    for(int i = 1; d[i]; i++) {
        insert(d[i]);
    }
    printf("%lld", solve());
    return 0;
}