题目连接：点击打开链接
解题思路：
manacher算法的模板题。
完整代码：
#include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#include <string>#include <cmath>#include <queue>using namespace std;typedef unsigned long long LL;const int MOD = int(1e9)+7;const int INF = 0x3f3f3f3f;const double EPS = 1e-9;const double PI = acos(-1.0); //M_PI;const int maxn = 2000001;int n;char s[maxn] , t[maxn];int len[maxn];void manacher(char t[]){int t_len = strlen(t);int mx = 0 , id;for(int i = 1 ; i < t_len ; i ++){if(mx > i) len[i] = min(len[id * 2 – i] , mx – i);else len[i] = 1;while(t[i + len[i]] == t[i – len[i]])len[i] ++;if(len[i] + i > mx){mx = len[i] + i;id = i;}}}void solve(char s[]){int s_len = strlen(s);int t_len = s_len * 2 + 2;t[0] = '+';for(int i = 0 ; i < t_len ; i ++){t[i * 2 + 1] = '#';t[i * 2 + 2] = s[i];}manacher(t);int ans = -INF;for(int i = 1 ; i < t_len ; i ++)ans = max(ans , len[i]);printf("%d\n" , ans – 1);}int main(){#ifdef DoubleQfreopen("in.txt","r",stdin);#endifwhile(~scanf("%d",&n)){for(int i = 0 ; i < n ; i ++){scanf("%s" , s);solve(s);}}return 0;}
，去旅行不在于记忆，而在于当时的那份心情。
