TOPALIN - Palindrome String

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
{$H+}
program TOPALIN;
const
  input  = '';
  output = '';
  maxk = 62;
var
  s: string;
  a: array[1..maxk,1..maxk] of boolean;
  free: array[1..maxk] of boolean;
  num: array[1..maxk] of integer;
  trans: array['0'..'z'] of integer;
  list: array[1..maxk] of integer;
  n,res,count: integer;

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

  readln(f, s);
  n := length(s);

  close(f);
end;

procedure DFS(u: integer);
var
  v: integer;
begin
  inc(count);
  list[count] := u;
  free[u] := false;

  for v := 1 to maxk do
    if free[v] and a[u,v] then DFS(v);
end;

procedure solve;
var
  i,j,u,v,sum,max: integer;
  ch: char;
begin
  count := 0;
  for ch := '0' to '9' do
    begin
      inc(count);
      trans[ch] := count;
    end;

  for ch := 'A' to 'Z' do
    begin
      inc(count);
      trans[ch] := count;
    end;

  for ch := 'a' to 'z' do
    begin
      inc(count);
      trans[ch] := count;
    end;

  fillchar(a, sizeof(a), false);

  fillchar(num, sizeof(num), 0);
  for i := 1 to n do
    begin
      u := trans[s[i]];
      v := trans[s[n + 1 - i]];

      inc(num[u]);
      if s[i] <> s[n + 1 - i] then a[u,v] := true;
    end;

  fillchar(free, sizeof(free), true);
  res := 0;

  for i := 1 to maxk do if free[i] then
    begin
      count := 0;
      DFS(i);
      sum := 0;
      max := 0;

      for j := 1 to count do
        begin
          sum := sum + num[list[j]];
          if max < num[list[j]] then max := num[list[j]];
        end;

      res := res + sum - max;
    end;
end;

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

begin
  init;
  solve;
  printresult;
end.

Download