PALINY - Palindrome dài nhất

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       50111;
  nkey          =       2;
  hkey          :       array[1..nkey] of longint=(
30011,30013);

var
  f1,f2         :       text;
  n,res         :       longint;
  a             :       array[1..MAXN] of longint;
  lt            :       array[1..nkey,0..MAXN] of longint;
  sum           :       array[1..nkey,0..1,0..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
      c:char;
    begin
      readln(f1,n);
      for i:=1 to n do
        begin
          read(f1,c);
          a[i]:=ord(c)-ord('a');
        end;
    end;

procedure init;
    var
      now,hashkey,i:longint;
    begin
      for now:=1 to nkey do
        begin
          hashkey:=hkey[now];
          lt[now,0]:=1;
          for i:=1 to n do
            lt[now,i]:=(lt[now,i-1]*26) mod hashkey;

          for i:=1 to n do
            sum[now,0,i]:=(sum[now,0,i-1]+lt[now,i-1]*a[i]) mod hashkey;
          for i:=n downto 1 do
            sum[now,1,i]:=(sum[now,1,i+1]+lt[now,n-i]*a[i]) mod hashkey;
        end;
    end;

function check(val:longint):boolean;
    var
      i,j,l1,l2,now:longint;
      ok:boolean;
    begin
      for i:=1 to n-val+1 do
        begin
          j:=i+val-1;
          l1:=i-1; l2:=n-j;
          if l1=l2 then begin l1:=0; l2:=0; end
          else if l1>l2 then begin l2:=l1-l2; l1:=0; end
          else begin l1:=l2-l1; l2:=0; end;

          ok:=true;
          for now:=1 to nkey do
            if (lt[now,l1]*(sum[now,0,j]-sum[now,0,i-1]+hkey[now])) mod hkey[now]
             <>(lt[now,l2]*(sum[now,1,i]-sum[now,1,j+1]+hkey[now])) mod hkey[now]
            then ok:=false;
          if ok then exit(true);
        end;
      exit(false);
    end;

function chan:longint;
    var
      l,r,mid,res:longint;
    begin
      l:=1; r:=n shr 1; res:=0;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if check(mid shl 1) then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res shl 1);
    end;

function le:longint;
    var
      l,r,mid,res:longint;
    begin
      l:=0; r:=n shr 1; res:=0;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if check(mid shl 1+1) then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res shl 1+1);
    end;

begin
  openF;
  inp;
  init;
  writeln(f2,max(chan,le));
  closeF;
end.

Download