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;
}