HDU3068 最长回文（Manacher算法）



链接： ttp://acm.hdu.edu.cn/showproblem.php?pid=3068

var

  p:array[1..1100000] of longint;

  s,s1:ansistring;

  mx,id,i,j,len,max:longint;

function min(a,b:longint):longint;

begin

  if a<=b then min:=a else min:=b;

end;

begin

  //assign(input,'manacher.in');reset(input);

  //assign(output,'manacher.out');rewrite(output);

  while not eof do begin

    fillchar(p,sizeof(p),0);

    readln(s);

    if s<>'' then begin

      i:=1;s1:=s;

      while i<=length(s1)*2+1 do begin

        insert('#',s,i);

        i:=i+2;

      end;

      id:=0;

      mx:=0;      max:=-maxlongint+1;

      for i:=1 to length(s) do begin

        if mx>i then p[i]:=min(p[2*id-i],mx-i)

        else p[i]:=1;

        j:=p[i];

        while true do begin

          inc(j);

          if (i+j-1>length(s)) or (i-j+1<=0) then break;

          if s[i+j-1]<>s[i-j+1] then break;

        end;

        dec(j);

        p[i]:=j;

        if p[i]+i>mx then begin

          mx:=p[i]+i;

          id:=i;

        end;

        if p[i]-1>max then max:=p[i]-1;

      end;

      writeln(max);

    end;

  end;

  readln;

  //close(input);close(output);

end.