. ARN

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuổi ARN đặc biệt được mã hóa bằng xâu S gồm các kí tự ‘A’, ‘U’, ‘G’, ‘X’. Họ muốn cắt một chuỗi ARN một mạch (được mã hóa bằng xâu X) cho trước.

Yêu cầu: từ chuỗi ARN S có thể cắt được tối đa bao nhiêu đoạn mạch X

Dữ liệu: vào từ tệp văn bản ARN.INP gồm:

• Dòng đầu gồm một xâu S mô tả chuỗi ARN.
• Dòng thứ 2 gồm một xâu X mô tả đoạn mạch cần cắt. (các xâu chỉ gồm các kí tự ‘A’, ‘U’, ‘G’, ‘X’ và độ dài xâu không quá 10³ kí tự

Kết quả: ghi ra tệp văn bản ARN.OUT kết quả của bài toán.

Ví dụ: