首页 > itarticle > BZOJ3676 – [Apio2014]回文串

BZOJ3676 – [Apio2014]回文串

admin 11月 12, 2020 0

求字符串 s 的回文子串长度乘以出现次数的最大值。

一道 PAM 的模板题。

其实 PAM 这个东西非常像 AC 自动机的，嘻嘻。

代码

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



#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = 300007;
typedef long long LL;

char str[SIZ];
int N;

int fal[SIZ], len[SIZ], siz[SIZ], nxt[SIZ][26], cnt, lst;

void addCh(int i, char ch) {
    int p = lst;
    while(str[i-len[p]-1] != str[i]) p = fal[p];

    if(!nxt[p][ch - 'a']) {
        int now = ++cnt, k = fal[p];
        len[now] = len[p] + 2;

        while(str[i-len[k]-1] != str[i]) k = fal[k];

        fal[now] = nxt[k][ch - 'a']; nxt[p][ch - 'a'] = now;
    }
    lst = nxt[p][ch - 'a'];
    siz[lst]++;
}

int main() {
    scanf("%s", str+1);
    N = strlen(str+1);

    cnt = 1;
    fal[0] = fal[1] = 1; len[1] = -1;

    for(int i=1;i<=N;i++) {
        addCh(i, str[i]);
    }

    LL ans = 0;
    for(int i=cnt;i;i--) {
        siz[fal[i]] += siz[i];
        ans = max(ans, 1LL * siz[i] * len[i]);
    }

    printf("%lldn", ans);
}