BÀI TẬP Ở NHÀ

https://www.baitaponha.com

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

Đây là câu 1 của đề thi học sinh giỏi tỉnh môn tin học năm 2015 - 2016. Mặc dù là câu 1 nhưng đây là một câu không phải quá dễ. Để xử lý được câu này thì cần có kỹ năng xử lý xâu. Trong bài này baitaponha.com xin trình bày cho các bạn các cách xử lý xâu. Vì bài dễ nên sẽ trình bày chi tiết nhằm cho các bạn mới tìm hiểu về Python cũng có thể hiểu được. Qua lời giải các bạn sẽ thấy điểm mạnh của Python là xử lý trong 1 dòng code.
Tìm xóa xâu con với 1 dòng lệnh
Bài 1. (6 điểm)                                       CENSOR
Cho một xâu S có độ dài tối đa là 106 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'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.
 

Tác giả: admin

Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây