UVALive_4975
可以先用Manacher算法预处理出每个字符i处的回文半径Ri，也就是最大的Ri使得i-Ri~i+Ri-1构成回文串。
之后枚举每个字符i作为wwRwwR中后面这个的wwR的起始字符，然后在[i-Ri/2,i-1]的范围内找到最小的j使得j+Rj>=i，如果存在这样的j，那么就存在一个长度为4*(i-j)的wwRwwR式的回文串。
#include#include #include #include #define INF 0x3f3f3f3f#define MAXD 300010int L, N, D, p[2 * MAXD], r[MAXD], tree[4 * MAXD];char str[MAXD], b[2 * MAXD];struct St{ int id, v; St(){} St(int _id, int _v) : id(_id), v(_v){} bool operator < (const St &t) const { return v > t.v; }};void prep(){ int i, id, max = 0; for(i = 0; str[i]; i ++) b[2 * i + 1] = '#', b[2 * i + 2] = str[i]; L = i, N = 2 * i + 1; b[0] = '$', b[N] = b[N + 1] = '#'; for(i = 1; i <= N; i ++) { p[i] = i < max ? std::min(max - i, p[2 * id - i]) : 1; while(b[i + p[i]] == b[i - p[i]]) ++ p[i]; if(i + p[i] > max) max = i + p[i], id = i; } for(i = 0; i < L; i ++) r[i] = (p[2 * i + 1] - 1) / 2;}void init(){ int i, j; scanf("%s", str); prep();}void update(int i){ for(; i ^ 1; i >>= 1) tree[i >> 1] = std::min(tree[i], tree[i ^ 1]);}int query(int x, int y){ int i = D + x - 1, j = D + y + 1, ans = INF; for(; i + 1 != j; i >>= 1, j >>= 1) { if(~i & 1) ans = std::min(ans, tree[i ^ 1]); if(j & 1) ans = std::min(ans, tree[j ^ 1]); } return ans;}void solve(){ int i, j, ans = 0; for(D = 1; D < L + 2; D <<= 1); memset(tree, 0x3f, sizeof(tree[0]) * 2 * D); std::priority_queue q; for(i = 0; i < L; i ++) { while(!q.empty()) { St st = q.top(); if(st.v >= i) break; q.pop(), tree[D + st.id] = INF, update(D + st.id); } q.push(St(i, i + r[i])), tree[D + i] = i, update(D + i); if(r[i] < 2) continue; j = query(i - r[i] / 2, i - 1); if(j != INF) ans = std::max(ans, 4 * (i - j)); } printf("%d\n", ans);}int main(){ int t; scanf("%d", &t); while(t --) { init(); solve(); } return 0;}