I test my code at my computer,I got a test which is filled by period string "abcde" and its length is 4000,and my program run only 0.25s.
My computer is:
Memory:3GB
System:Windows XP
CPU:1.66GHZ
But I got tle at #32...Why???
Here is my code.
var
        i,j,xx,ox,t,l:longint;
        s:ansistring;
        f,x:array [1..4010] of longint;
        o:array [0..4010] of boolean;
function pdhw(l,r:longint):boolean;
var
        i:longint;
begin
        if l=r then exit(true);
        for i:=l to (l+r)>>1+1 do
          if s[i]<>s[r+l-i] then exit(false);
        exit(true);
end;
begin
        readln(s);
        l:=length(s);
        for i:=1 to l do
        begin
          f[i]:=maxlongint;
          if pdhw(1,i) then f[i]:=0
          else for j:=1 to i-1 do
                 if (f[i]>f[j]+1)and(pdhw(j+1,i)) then begin
                   f[i]:=f[j]+1;
                   x[i]:=j;
                 end;
        end;
        writeln(f[l]+1);
        xx:=l;
        repeat
          ox:=xx;
          xx:=x[xx];
          if ox=l then o[xx+1]:=true
          else o[xx+1]:=true;
        until xx=0;
        o[1]:=false;
        for i:=1 to length(s) do
          if o[i] then write(' ',s[i])
          else write(s[i]);
end.