1 条题解
-
0

#include <bits/stdc++.h> #define N 341467 #define count scx using namespace std; typedef long long ll; char s[N], *ptr; int d[N][26], fail[N], val[N], count[N]; int i, cnt = 1, p, last = 0; ll ans = 0; inline void up(ll &x, const ll y) {x < y ? x = y : 0;} int get_fail(int x) {for(; *(ptr - (val[x] + 1)) != *ptr; x = fail[x]); return x;} void extend(int x){ p = get_fail(last); int &q = d[p][x]; if(!q) {fail[++cnt] = d[get_fail(fail[p])][x]; val[q = cnt] = val[p] + 2;} ++count[last = q]; } int main(){ s[0] = val[1] = -1; fail[0] = 1; scanf("%s", s + 1); for(ptr = s; *ptr; ++ptr) extend(*ptr - 'a'); for(i = cnt; i > 1; --i) count[fail[i]] += count[i]; for(i = 2; i <= cnt; ++i) up(ans, (ll)count[i] * val[i]); printf("%lld\n", ans); return 0; }
- 1
信息
- ID
- 5341
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者