显然可以先贪心地取互为反串的最长前后缀。
取完扔掉之后，相当于要在剩下的字符串的前缀或后缀找到一个最长的回文串。
manacher 即可，时间复杂度 $\mathcal O(n)$。
```cpp
const int N = 1e6 + 7;
int n, m;
char s[N], t[N];
inline int work(char *s, int n) {
string ss = "$#";
vi p;
for (int i = 1; i <= n; i++) ss += s[i], ss += "#";
p.pb(1);
int mx = 0, id = 0, ans = 1;
for (int i = 1; i < (int)ss.length(); i++) {
p.pb(mx > i ? min(p[2*id-i], mx - i) : 1);
while (i + p[i] < (int)ss.length() && ss[i+p[i]] == ss[i-p[i]]) ++p[i];
if (i == p[i]) ans = max(ans, p[i]);
if (i + p[i] > mx) mx = i + p[i], id = i;
}
return ans - 1;
}
inline void solve() {
rds(s, n);
int p = 1;
while (p <= n && s[p] == s[n+1-p]) ++p;
if (p == n + 1) {
for (int i = 1; i <= n; i++) putchar(s[i]);
return puts(""), void();
}
m = 0;
for (int i = p; i <= n + 1 - p; i++) t[++m] = s[i];
int l = work(t, m);
reverse(t + 1, t + m + 1);
int r = work(t, m);
reverse(t + 1, t + m + 1);
if (l < r) reverse(t + 1, t + m + 1), swap(l, r);
for (int i = 1; i < p; i++) putchar(s[i]);
for (int i = 1; i <= l; i++) putchar(t[i]);
for (int i = p - 1; i; i--) putchar(s[i]);
puts("");
}
int main() {
int T;
rd(T);
while (T--) solve();
return 0;
}
```