提交记录 Manacher跑两遍，中心扩展跑一遍，时间复杂度不是一样的吗？

// Problem: D2. Prefix-Suffix Palindrome (Hard version)
// Contest: Codeforces - Codeforces Global Round 7
// URL: https://codeforces.com/problemset/problem/1326/D2/
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll  = long long;
using ull = unsigned long long;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(v)  (int)v.size()
#define all(v) v.begin(),v.end()
#define imax(a,b) ((a)>(b)?(a):(b))
#define imin(a,b) ((a)<(b)?(a):(b))
#define mem(a,v) memset(a,(v),sizeof(a))
#define MT int T; cin>>T; while(T--)
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define rep_(i,a,b) for(int i=a; i>=b; i--)
#define de(a) cout<<(a)<<'\n'
#define de2(a,b) cout<<(a)<<' '<<(b)<<'\n'
#define eps 1e-6

const int inf = INT_MAX;
const ll llinf = LLONG_MAX;

ll gcd(ll a, ll b) {return b==0?a:gcd(b,a%b);}

#define N (int)1e6+10
int n,l,r,c;
string S;
string getmax(string s){
	n = sz(s);
	vector<int> lmx(n),rmx(n);
	rep(i,0,2*n-1){
		l=i/2;
		r=l+(i%2);
		while(l>=0 && r<n and s[l]==s[r]){
		    // [0...l-1[l..r]r+1...n-1]
			if(r-l+1 + 2*l <= n) lmx[l]=max(lmx[l],r-l+1); //不重叠下的最大值
			if(r-l+1 + 2*(n-(r+2)) <= n) rmx[r]=max(rmx[r],r-l+1);
			l--;r++;
		}
	}
	int ans = lmx[0]; //最长回文前缀
	string res = s.substr(0,ans);
	if(rmx[n-1] > ans){
		res = s.substr(n-rmx[n-1],rmx[n-1]);
	}
	return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    MT{
    	cin>>S;
    	n = sz(S);
    	c=0;
        l=0,r=n-1;
    	while(l<r){
    		if(S[l]!=S[r]){
				string t = S.substr(0,c),tt=t;
				reverse(all(tt));
				de( t + getmax(S.substr(l,r-l+1)) + tt);
    			goto end1;
    		}
    		c++;
    		l++,r--;
    	}
    	de(S);
    	end1:;
    }
    return 0;
}