TLE in EPALIN - is O(n) fast enough?

[aristofanis]

Hi, I'm trying to solve the problem EPALIN (spoj.com/problems/EPALIN/). My approach is the manacher's algorithm, which is said to have lineral complexity (O(n)). But I get TLE I don't understand what is wrong with my solution, and I don't know if it's the implementation which causes the TLE, or if I'm using the wrong algorithm. Please, help. Thanks in advance.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
inline int min(int a, int b) { return (a<b?a:b); }
void putR(char *s, int n) { for(int i=n-1; i>=0; --i) putchar(s[i]); }
void change(const char *s, char *&t, int n) {
  int tn=n*2+3;
  t=new char[tn]; t[0]='^';
  for(int i=0, j=1; i<n; ++i) {
    t[j]='#'; t[++j]=s[i]; ++j;
  }
  t[tn-2]='#'; t[tn-1]='$'; 
}
char s[200002];
int main() {
  char *t;
  while(gets(s)) {
    int size=strlen(s);
    int lo=0, hi=size-1;
    while(lo<hi) {
      char tmp=s[lo];
      s[lo]=s[hi];
      s[hi]=tmp;
      lo++; hi--;
    }
    change(s, t, size);
    int n=strlen(t), *P=new int[n];
    int C=0, R=0;
    for(int i=1; i<n-1; ++i) {
      int it=2*C-1;
      P[i] = ( R>i ? min(R-i, P[it]) : 0 );
      while(t[i+1+P[i]] == t[i-1-P[i]]) P[i]++;
      if(i+P[i] > R) { C=i; R=i+P[i]; }
    }
    int cent=0, index=0;
    int pali=0;
    for(int i=1; i<n-1; ++i, ++index) {
      if(P[i] >= pali) {
        if(P[i] == index) {
          pali=P[i];
          cent=i;
        }
      }
    }
    putR(s, strlen(s));
    for(int i=cent-1; i<size; ++i) {
      putchar(s[i]);
    }
    printf("\n");
  }
  return 0;
}