1 条题解
-
0
#include <bits/stdc++.h> using namespace std; string tempS, s; int P[112345 * 2]; // 以 i 开头的最长回文串 int f[112345 * 2]; // 以 i 结尾的最长回文串 int g[112345 * 2]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> tempS; s = "^"; s += "#"; for (int i = 0; i < tempS.length(); i++) s += tempS[i], s += "#"; s += "$"; int n = s.length(); // manacher int C, R; C = R = 0; for (int i = 1; i < n - 1; i++) { int i_mirror = 2 * C - i; // C - i_mirror = i - C if (R > i) P[i] = min(R - i, P[i_mirror]); else P[i] = 0; while (s[i + P[i] + 1] == s[i - P[i] - 1]) P[i]++; f[i - P[i]] = max(f[i - P[i]], P[i]); g[i + P[i]] = max(g[i + P[i]], P[i]); if (i + P[i] > R) { C = i; R = i + P[i]; } } for (int i = 3; i <= n - 2; i++) f[i] = max(f[i], f[i - 2] - 2); for (int i = n - 4; i >= 1; i--) g[i] = max(g[i], g[i + 2] - 2); /* cout << s << endl; for (int i = 0; i < n; i++) cout << P[i]; cout << endl; for (int i = 0; i < n; i++) cout << f[i]; cout << endl; for (int i = 0; i < n; i++) cout << g[i]; cout << endl; */ int ans = 0; for (int i = 1; i <= n - 2; i++) if (s[i] == '#' && f[i] && g[i]) ans = max(ans, f[i] + g[i]); cout << ans << "\n"; return 0; }
信息
- ID
- 1359
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者