Can I ask why my solution give TLE?
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define oo 0x7f7f7f7f
#define fi "PALDR.inp"
#define fo "PALDR.out"
#define NMAX 2000010
#define sqr(n) (n)*(n)
#define sz(a) int(a.size())
#define CLR(a,i) memset(a,i,sizeof(a))
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Ford(i,a,b) for(int i=a;i>=b;--i)
#define REP(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(int i=1;i<=n;++i)
#define REPD(i,n) for(int i=n-1;i>=0;--i)
typedef long long ll;
int P[NMAX];
char S[NMAX],T[NMAX];
bool f[NMAX];
//
int main()
{
#ifndef ONLINE_JUDGE
freopen(fi,"r",stdin);
//freopen(fo,"w",stdout);
#endif
int test;
scanf("%d\n",&test);
while (test) {
gets(S);
if (strlen(S)==0) continue; else --test;
int NN=1;
strcat(T,".#");
REP(i,int(strlen(S))) {
T[++NN]=S[i]; T[++NN]='#';
}
//cout<<S<<" ";
int C=0,R=0;
bool stop=false;
//----------------------------------------------------Start Manacher
CLR(f,false); f[1]=true;
FOR(i,1,NN) {
int im=2*C-i;
P[i]=0;
///----------------------------------
P[i]=(R>=i)?min(R-i,P[im]):0;
while (T[i+P[i]+1]==T[i-P[i]-1]) ++P[i];
if (i+P[i]>R) { C=i; R=i+P[i]; }
///----------------------------------
for(int dem=1;2*dem<=P[i]; ++dem) {
int len=dem*2;
if (f[i-len]) {
f[i+len]=true;
if (i+len==NN) { //-------------------------------------- if reach to to last character: check true and stop right away
stop=true;
printf("YES\n");
break;
}
}
}
if (stop) break;
///----------------------------------
}
if (!stop) printf("NO\n");
}
return 0;
}
