# bzoj 3676: [Apio2014]回文串 回文自动机

xiaoxiao2021-02-28  7

### bzoj 3676: [Apio2014]回文串

#### Sample Input

【样例输入l】 abacaba 【样例输入2] www

#### Sample Output

【样例输出l】 7 【样例输出2] 4

### 代码

/************************************************************** Problem: 3676 User: 2014lvzelong Language: C++ Result: Accepted Time:752 ms Memory:37616 kb ****************************************************************/ #include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<cmath> using namespace std; const int N = 310000; long long ans; int len[N], f[N], a[N], val[N], ch[N][26], last, sz, n; void PDT_pre() { f[last = sz = 0] = 1; len[++sz] = a[n = 0] = -1; } void Extend(int c) { a[++n] = c; int p, np, x; for(p = last; a[n - len[p] - 1] != a[n]; p = f[p]) ; if(!ch[p][c]) { len[np = ++sz] = len[p] + 2; for(x = f[p]; a[n - len[x] - 1] != a[n]; x = f[x]) ; f[np] = ch[x][c]; ch[p][c] = np; } ++val[last = ch[p][c]]; } void work() { char ch = getchar(); while(ch < 'a' || ch > 'z') ch = getchar(); for(;ch >= 'a' && ch <= 'z'; ch = getchar()) Extend(ch - 'a'); } int main() { PDT_pre(); work(); for(int i = sz; i >= 2; --i) { val[f[i]] += val[i]; ans = max(ans, 1LL * val[i] * len[i]); } printf("%lld\n", ans); return 0; }