HTML:

Ví dụ 6. Cho xâu s (ñộ dài không vượt quá 10^6 chỉ gồm 2 kí tự 'A' và 'B'. đếm số cách chọn cặp chỉ số (i,j) mà xâu con liên tiếp từ kí tự thứ i ñến kí tự thứ j của xâu s có số lượng kí tự 'A' bằng số lượng kí tự 'B'.

Dữ liệu vào trong file “AB.INP” có dạng:

gồm một dòng duy nhất chứa xâu s

Kết quả ra file “AB.OUT”

có dạng:gồm một dòng duy nhất chứa một số là kết quả bài toán.

AB.INP AB.OUT

ABAB 4

const MAX =1000000;

fi ='AB.INP';

fo ='AB.OUT';

var s :ansistring;

c :array[-MAX..MAX]of longint;

f :text;

i, sum :longint;

count :int64;

BEGIN

assign(f,fi); reset(f);

read(f,s);

close(f);

fillchar(c,sizeof(c),0);

c[0]:=1;

sum:=0;

count:=0;

for i:=1 to length(s) do begin

if s[i]='A' then sum:=sum - 1

else sum:=sum + 1;

count:=count + c[sum];

inc(c[sum]);

end;

assign(f,fo); rewrite(f);

write(f,count);

close(f);

END.

Bài tập