QBPAL - Đếm chuỗi đối xứng

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  MAXN=200;
  oo=10;
type
  bigNum=array[0..MAXN] of longint;
var
  s:string;
  n:longint;
  d:array[0..MAXN,0..MAXN] of bigNum;
operator +(a,b:bigNum) c:bigNum;
var
  nho,i:longint;
begin
  nho:=0;
  fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]);
  for i:=MAXN downto MAXN-c[0]+1 do
    begin
      c[i]:=a[i]+b[i]+nho;
      nho:=c[i] div oo;
      c[i]:=c[i] mod oo;
    end;
  if nho>0 then
    begin
      inc(c[0]);
      c[MAXN-c[0]+1]:=nho;
    end;
end;
operator -(a,b:bigNum) c:bigNum;
var
  nho,i:longint;
begin
  nho:=0;
  fillchar(c,sizeof(c),0); c[0]:=a[0];
  for i:=MAXN downto MAXN-c[0]+1 do
    begin
      c[i]:=a[i]-b[i]-nho;
      if c[i]<0 then
        begin
          nho:=1;
          c[i]:=c[i]+oo;
        end
      else nho:=0;
    end;
  while (c[0]>0) and (c[MAXN-c[0]+1]=0) do dec(c[0]);
end;
procedure solve;
var
  i,j,k:longint;
  a:bigNum;
begin
  fillchar(a,sizeof(a),0);
  a[0]:=1; a[200]:=1;
  for i:=1 to n do d[i,i]:=a;
  for k:=1 to n do
  for i:=1 to n-k do
    begin
      j:=i+k;
      if s[i]=s[j] then d[i,j]:=d[i,j-1]+d[i+1,j]+a
      else d[i,j]:=d[i,j-1]+d[i+1,j]-d[i+1,j-1];
    end;
end;
procedure print(a:bigNum);
var
  i:longint;
  s:string;
begin
  if a[0]=0 then begin writeln(0); exit; end;
  write(a[MAXN-a[0]+1]);
  for i:=MAXN-a[0]+2 to MAXN do write(a[i]);
  writeln;
end;
begin
  readln(s); n:=length(s);
  solve;
  print(d[1,n]);
end.

Download