TOPALIN - Palindrome String

Tác giả: ladpro98

Ngôn ngữ: Pascal

program TOPALIN;
uses    math;
const   fi='';
var     a:ansistring;
        chk:array[1..100] of boolean;
        mat:array[1..100,1..100] of longint;
        w:array[1..100] of longint;
        num:array['0'..'z'] of longint;
        inp:text;
        i,n,res,sum,maxV,t:longint;
        c:char;

procedure dfs(i:longint);
var     j:longint;
begin
        chk[i]:=true;
        inc(sum,w[i]);
        maxV:=max(maxV,w[i]);
        for j:=1 to t do
        if (mat[i,j]=1) and (not chk[j]) then
        dfs(j);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,a);close(inp);
        n:=length(a);t:=0;
        for c:='A' to 'z' do begin
                inc(t);num[c]:=t;
        end;
        for c:='0' to '9' do begin
                inc(t);num[c]:=t;
        end;
        for i:=1 to n div 2 do
        if a[i]<>a[n-i+1] then begin
                mat[num[a[i]],num[a[n-i+1]]]:=1;
                mat[num[a[n-i+1]],num[a[i]]]:=1;
        end;
        for i:=1 to n do inc(w[num[a[i]]]);
        for i:=1 to t do
        if not chk[i] then begin
                sum:=0;maxV:=0;
                dfs(i);
                res:=res+sum-maxV;
        end;
        write(res);
end.

Download