Template <Manacher>-526互联

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// O(n) 计算字符串s的每个字符的最大回文半径，返回最长回文子串长度
int Manacher(string s)
{
	// 空字符串直接返回0
    if (s.length() == 0) return 0;

	// manacher 扩展后串长度
    int len = (int)(s.length() * 2 + 1); 
	// 扩展后manacher字符串 （下标从1开始）
	string ms = "$#";
	for (auto ch: s) 
	{
		ms += ch; 
		ms += '#'; 
	} 
	// maxr[i] 表示以ms[i]为回文字串的对称中心，最大回文半径
	// 如 aabaa 的回文中心为 b， 回文半径 maxr = 3
	vector<int> maxr(len+1, 0);
    // 当前最右侧回文子串下标r， 该串的回文中心c， 当前最大回文半径 maxl
	int r = -1, c = -1, maxl = 0;
	for (int i = 1; i <= len; i ++)
	{
		if (i <= r) maxr[i] = min(r - i + 1, maxr[c * 2 - i]);  // 当i不超过当前最右侧回文边界，则可对称O(1)得到答案
		else maxr[i] = 1;  	// 若超过当前最右侧边界，则需要暴力比较，回文半径初始为1，即一个字符
		while (i - maxr[i] >= 1 and i + maxr[i] <= len and ms[i-maxr[i]] == ms[i+maxr[i]])  // 不越界，两侧字符相同
			maxr[i] ++;  	// 回文半径+1
		maxl = max(maxl, maxr[i]);  // 更新最大回文半径
		if (i + maxr[i] - 1 > r)  	// 更新最右侧边界
		{
			r = i + maxr[i] - 1;
			c = i;
		}
	}
	int res = maxl - 1;  // 原串s的最大回文子串长度=扩展串ms的最大回文半径-1
	return res;
}

int main()
{
    int T = 1; cin >> T;
    while (T --)
    {
        string s; cin >> s;
        cout << Manacher(s) << endl;
    }
    return 0;
}