38 lines
1.1 KiB
C++
38 lines
1.1 KiB
C++
struct Eertree {
|
|
int len[N], link[N], nxt[N][26], r[N];
|
|
long long cnt[N]; int sz, last, n;
|
|
char s[N];
|
|
Eertree() {
|
|
memset(nxt, 0, sizeof(nxt));
|
|
memset(cnt, 0, sizeof(cnt));
|
|
s[0] = -1;
|
|
n = 0; sz = 2; last = 1;
|
|
len[0] = -1; link[0] = 0;
|
|
len[1] = 0; link[1] = 0;
|
|
}
|
|
int get_link(int v) {
|
|
while (s[n-len[v]-1] != s[n]) v = link[v];
|
|
return v;
|
|
}
|
|
void insert(char c) {
|
|
s[++n] = c;
|
|
int cur = get_link(last);
|
|
if (!nxt[cur][c-'a']) {
|
|
int now = sz++;
|
|
r[now] = n;
|
|
len[now] = len[cur] + 2;
|
|
if (len[now] == 1) link[now] = 1;
|
|
else link[now] = nxt[get_link(link[cur])][c-'a'];
|
|
nxt[cur][c-'a'] = now;
|
|
}
|
|
last = nxt[cur][c-'a'];
|
|
cnt[last]++;
|
|
}
|
|
void propagate() { fore(i, sz-1, 2) cnt[link[i]] += cnt[i]; }
|
|
};
|
|
|
|
Eertree et; forr(i, n) et.insert(s[i]);
|
|
int m = et.sz; et.propagate();
|
|
fors(i, 2, m-1) ans = max(ans, et.cnt[i] * et.len[i]);
|
|
// node i : s[(et.r[i]-et.len[i]+1)~(et.r[i])]
|
|
// distinct count of pal : m-2; count of node i : et.cnt[i];
|