Censor | Câu 1 - Đề HSG tin 11 | Nghệ An năm 2015 -2016

Bài 1. (6 điểm)                                       CENSOR
Cho một xâu S có độ dài tối đa là 10⁶ ký tự. Trong xâu S người ta loại bỏ sự xuất hiện của một xâu con T có độ dài ≤ 100 ký tự. Để làm điều này, người ta tìm sự xuất hiện của T lần đầu tiên trong S và xóa nó. Sau đó cứ lặp đi lặp lại quá trình này cho đến khi không còn sự xuất hiện của T trong S. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một sự xuất hiện mới của T chưa từng tồn tại trước đó. Hãy xác định nội dung cuối cùng của xâu S.
Dữ liệu: Vào từ file văn bản CENSOR.INP:

• Dòng đầu tiên chứa xâu S.
• Dòng thứ hai chứa xâu T. Chiều dài của xâu T bé hơn chiều dài của S, và tất cả các kí tự của S và T đều là ký tự thường (trong phạm vi từ a..z).

Kết quả: Ghi ra file văn bản CENSOR.OUT chỉ một dòng chứa xâu S sau khi đã xóa bỏ hết T. Đảm bảo rằng S sẽ không trở nên xâu rỗng trong quá trình xóa.
Ví dụ

CENSOR.INP	CENSOR.OUT
whatthemomooofun moo	whatthefun

Cách 1:

Trong cách này chúng ta sẽ dùng phương thức find để tìm vị trí xuất hiện của xâu t trong xâu s. với phương thức find sẽ trả về vị trí ký tự đầu tiên của t xuất hiện trong s nếu tìm thấy t, còn không thì sẽ trả về giá trị là -1.
Ví dụ: s = 'hello' và t = 'llo' thì j = s.find(t) sẽ có giá trị là j = 2.
Sau khi tìm được vị trí t trong s, ta dùng kỹ thuật cắt xâu để cập nhật lại xâu s như sau: s = s[:j] + s[j + len(t):].

Code cách 1:

def censor(s, t):
    while len(t) < len(s):
        j = s.find(t)
        if j == -1:
            break
        s = s[:j] + s[j + len(t):]
    return s
if __name__ == "__main__":
    with open("CENSOR.INP", "r") as f:
        s = f.readline().strip()
        t = f.readline().strip()

    with open("CENSOR.OUT", "w") as f:
        f.write(censor(s, t))

Cách 2:

Để gọn code hơn ta sử dụng phương thức replace trong python. Phương thức replace dùng để thay thể chuỗi con t trong s thành chuỗi rỗng: s = s.replace(t,''). Như vậy chúng ta chỉ cần một dòng code: while t in s and len(t)<=len(s): s = s.replace(t,'') là đã xử lý xong bài toán.

Code cách 2:

with open("CENSOR.INP", "r") as f:
    s = f.readline().strip()
    t = f.readline().strip()

while t in s and len(t) <= len(s): s = s.replace(t,'')

with open("CENSOR.OUT", "w") as f:
    f.write(s)

Code mẫu bằng Pascal:

const fi='censor.inp';
      fo='censor.out';
var
     f:text;
     t,s:ansistring;

procedure doc;
   begin
      assign(f,fi);
      reset(f);
      readln(f,s);
      readln(f,t);
      close(f);
   end;

procedure xuli;
var i:longint;
    tg,st:ansistring;
  begin
     st:='';
     for i:=1 to length(s) do
       begin
          st:=st+s[i];
          if length(st)>=length(t) then
          begin
          tg:=copy(st,length(st)-length(t)+1,length(t));
          if tg=t then delete(st,length(st)-length(t)+1,length(t));
          end;
       end;
     assign(f,fo);
     rewrite(f);
     writeln(f,st);
     close(f);
  end;

BEGIN
        doc;
        xuli;
END.