Dịch đề A. Two Substrings – Codeforces 306 (Div. 2)
Cho một xâu s. Nhiệm vụ của bạn là xác định xâu s có chứa 2 xâu con “AB”, “BA” không chồng chéo lên nhau (AB, BA nằm ở vị trí bất kì).
input
Dòng duy nhất của input có chứa một chuỗi s có chiều dài từ 1 đến 10^5 gồm các chữ Latin viết hoa.
Output
ghi “YES” (không có dấu ngoặc kép), nếu chuỗi s chứa hai chuỗi con không chồng “AB” và “BA”, và “NO” nếu không.
Chú Ý
Trong test mẫu đầu tiên, mặc dù thực tế rằng có những chuỗi con “AB” và “BA”, nhưng sự xuất hiện của nó chồng chéo lên nhau, vì vậy câu trả lời là “NO”.
Trong Test mẫu thứ hai BACFAB có đầy đủ AB và BA không họ không trùng nhau, nên kết quả là YES
Trong test thứ ba không có xâu “AB” cũng không có xâu”BA”.
Hướng dẫn giải A. Two Substrings – Codeforces 306 (Div. 2)
– Sẽ có 2 loại kết quả dẫn đến đáp án “YES” đó là AB đứng trước BA và BA đứng trước AB
– Đầu tiên xử lí trường hợp AB đứng trước BA: duyệt tìm xâu con “AB” đầu tiên của S, duyệt tìm xâu con “BA” ở cuối dãy xuất hiện đầu tiên của s. Nếu vị trí AB tìm được nằm trước vị trí BA thì kết quả là YES,
– Tương tự trường hợp BA đứng trước AB
– Lưu ý trường hợp với dạng test là “ABA”
– các kết quả còn lại đều là “NO”
Code tham khảo A. Two Substrings – Codeforces 306 (Div. 2)
[sociallocker]
const fi='';
nmax=100000;
type data=longint;
var
f:text;
A:array[0..nmax+1] of char;
n:data;
procedure xuli;
var i,j:data;
begin
assign(f,fi); reset(f);
N:=0;
while not eoln(f) do
begin
inc(n);
read(f,a[n]);
end;
close(f);
for i:=1 to n-1 do // AB
if a[i]+a[i+1]='AB' then
break;
for j:=n-1 downto 1 do // BA
if a[j]+a[j+1]='BA' then
break;
if i+1<j then
begin
writeln('YES');
halt;
end;
for i:=1 to n do // BA
if a[i]+a[i+1]='BA' then
break;
for j:=n-1 downto 1 do // AB
if a[j]+a[j+1]='AB' then
break;
if i+1<j then
begin
writeln('YES');
halt;
end;
writeln('NO');
end;
begin
xuli;
end.[/sociallocker]
