这道题，我的大致思想是先用manacher求出所有回文串，然后用刚好拼接在一起的两个回文串的总长的最大值更新答案。
manacher是O(n)的，但是暴力的枚举回文中心能达到O(n2)，所以得想办法优化枚举。
令pre[i]表示离 i最远且左半部分包含 i 的回文串的回文中心的位置，suf[i]表示离 i 最远且右半部分包含 i 的回文串的回文中心的位置。有人会问，为什么是包含，而不是到 i 结束的回文串？因为最优解对于这个回文串可能取不完，比如说abaab，单纯看aba的话，只能取到ab + a = abaa，但实际上应该是a + baab = abaab。维护好这两个数组后，ans = max(suf[i] - pre[i])。
这两个数组的维护跟manacher有点像：对于pre，建一个指针 j，然后扫维护好的回文半径数组，每一次把[j, i + p[i])的pre都更新成 i。suf的维护反过来即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n; 38 char s[maxn], t[maxn << 1]; 39 int p[maxn << 1]; 40 41 void init() 42 { 43 n = strlen(s); 44 t[0] = '@'; 45 for(int i = 0; i < n; ++i) t[i << 1 | 1] = '#', t[(i << 1) + 2] = s[i]; 46 n = (n + 1) << 1; 47 t[n - 1] = '#'; t[n] = '$'; 48 } 49 int pre[maxn << 2], suf[maxn << 2]; 50 void manacher() 51 { 52 int mx = 0, id; 53 for(int i = 1; i < n; ++i) 54 { 55 if(i < mx) p[i] = min(p[(id << 1) - i], mx - i); 56 else p[i] = 1; 57 while(t[i - p[i]] == t[i + p[i]]) p[i]++; 58 if(i + p[i] > mx) mx = i + p[i], id = i; 59 } 60 } 61 62 int main() 63 { 64 scanf("%s", s); 65 init(); manacher(); 66 for(int i = 1, j = 1; i < n; ++i) 67 for(; j < i + p[i]; ++j) pre[j] = i; 68 for(int i = n - 1, j = n - 1; i; --i) 69 for(; j > i - p[i]; --j) suf[j] = i; 70 int ans = 0; 71 for(int i = 1; i < n; ++i) ans = max(ans, suf[i] - pre[i]); 72 write(ans); enter; 73 return 0; 74 }