# 算法

a, b, c, aa, aaa

abcaaa

a, b, c, aa, aaa

# 例题

[Apio2014] 回文串 BZOJ – 3676

#include <bits/stdc++.h>

#define NS (300005)

using namespace std;

typedef long long LL;

int n;

char s[NS];

LL ans;

struct PAM
{
int n, nxt[NS][26], pre[NS], len[NS], cnt[NS], sz;
PAM() { pre[0] = pre[1] = sz = 1, len[1] = -1; }
void run(char (&s)[NS])
{
n = strlen(s + 1);
for (int i = 1, p = 0; i <= n; i += 1)
{
while (s[i - len[p] - 1] != s[i]) p = pre[p];
if (!nxt[p][s[i] - 'a'])
{
int a = ++sz, b = pre[p];
len[a] = len[p] + 2;
while (s[i - len[b] - 1] != s[i]) b = pre[b];
pre[a] = nxt[b][s[i] - 'a'], nxt[p][s[i] - 'a'] = a;
}
p = nxt[p][s[i] - 'a'], cnt[p]++;
}
}
void cal()
{
for (int i = sz; i > 1; i -= 1)
cnt[pre[i]] += cnt[i], ans = max(ans, 1ll * len[i] * cnt[i]);
}
} pam;

int main(int argc, char const* argv[])
{
scanf("%s", s + 1), pam.run(s), pam.cal(), printf("%lld\n", ans);
return 0;
}


#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

struct PAM
{
int n, nxt[NS][26], pre[NS], len[NS], sz, mx[NS];
PAM() { pre[0] = pre[1] = sz = 1, len[1] = -1; }
void run(char (&s)[NS])
{
n = strlen(s + 1);
for (int i = 1, p = 0; i <= n; i += 1)
{
while (s[i - len[p] - 1] != s[i]) p = pre[p];
if (!nxt[p][s[i] - 'a'])
{
int a = ++sz, b = pre[p];
len[a] = len[p] + 2;
while (s[i - len[b] - 1] != s[i]) b = pre[b];
pre[a] = nxt[b][s[i] - 'a'], nxt[p][s[i] - 'a'] = a;
}
p = nxt[p][s[i] - 'a'], mx[i] = len[p];
}
}
} p1, p2;

char s[NS];

int n, ans;

int main(int argc, char const* argv[])
{
scanf("%s", s + 1), n = strlen(s + 1);
p1.run(s), reverse(s + 1, s + 1 + n), p2.run(s);
reverse(p2.mx + 1, p2.mx + 1 + n);
for (int i = 1; i < n; i += 1) ans = max(ans, p1.mx[i] + p2.mx[i + 1]);
printf("%d\n", ans);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.