HAI CHUỖI GỌI LÀ GẦN ĐÚNG KHI CÁC KÝ TỰ CỦA CHUỖI GỐC XUẤT HIỆN TRONG CHUỖI KIA THEO ĐÚNG THỨ TỰ NHƯ CHUỖI GỐC

Bài 2 (10 điểm): Chuỗi gần đúng.

Hai chuỗi gọi là gần đúng khi các ký tự của chuỗi gốc xuất hiện trong chuỗi kia

theo đúng thứ tự như chuỗi gốc. Số kí tự sai khác được tính thành tỉ lệ phần trăm so

với chuỗi có độ dài lớn hơn. Nếu tỉ lệ % sai khác không lớn hơn m% thì ta gọi đây

là 2 chuỗi gần đúng.

Ví dụ: xem hình sau:

Trong hình trên, độ sai lệch giữa mispeld và misspelled là 3 kí tự; tỉ lệ là 3/10

tức 30%.

* Yêu cầu: Viết chương trình tìm các chuỗi gần đúng so với chuỗi gốc.

Fie dữ liệu vào cho trong File BAI2.INP. Hàng đầu tiên là m (số nguyên giá trị

từ 1 đến 50). Hàng kế tiếp là chuỗi gốc; các hàng còn lại là các chuỗi cần xác định

có gần đúng với chuỗi gốc đã cho hay không. Chuỗi chỉ gồm các kí tự chuẩn trong

bảng mã ASCII và không có khoảng trắng trong chuỗi; chiều dài chuỗi không quá

254 kí tự.

Kết quả ghi trong File dữ liệu ra BAI2.OUT; gồm chuỗi gốc và các chuỗi gần

đúng với chuỗi gốc (không phân biệt chữ hoa/thường). Mỗi chuỗi được ghi trên 1

hàng.

Ví dụ:

BAI2.INP BAI2.OUT

30 mispeld

mispeld misspelled

misplace

misspelled

mislead