PALINY - Palindrome dài nhất

Tác giả: ll931110

Ngôn ngữ: Pascal

program PALINY;
uses math;
const
  input  = '';
  output = '';
  maxn = 50000;
var
  a: array[0..maxn] of char;
  rad: array[0..maxn] of longint;
  res,n: longint;

procedure init;
var
  f: text;
  i: longint;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 0 to n - 1 do read(f, a[i]);

  close(f);
end;

procedure solve;
var
  i,j,k: longint;
begin
  res := 0;

  i := 0;
  j := 0;
  while i < n do
    begin
      while (i >= j) and (i + 1 + j < n) and (a[i - j] = a[i + 1 + j]) do inc(j);
      rad[i] := j;

      k := 1;
      while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
        begin
          rad[i + k] := min(rad[i - k],rad[i] - k);
          inc(k);
        end;

      j := max(j - k,0);
      i := i + k;
    end;

  for i := 0 to n - 1 do if res < rad[i] * 2 then res := rad[i] * 2;

  i := 0;
  j := 0;
  while i < n do
    begin
      while (i >= j) and (i + 2 + j < n) and (a[i - j] = a[i + 2 + j]) do inc(j);
      rad[i] := j;

      k := 1;
      while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
        begin
          rad[i + k] := min(rad[i - k],rad[i] - k);
          inc(k);
        end;

      j := max(j - k,0);
      i := i + k;
    end;

  for i := 0 to n - 1 do if res < rad[i] * 2 + 1 then res := rad[i] * 2 + 1;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Download