Trong bài học về xâu ký tự, bạn Bình đố lại bạn An câu đố như sau: Cho 2 xâu ký tự chỉ gồm các ký tự latinh in thường từ ‘a’ đến ‘z’ cần phải xóa một số lượng ít nhất ký tự có thể (có thể không xóa ký tự nào) để nhận được hai xâu có ký tự giống nhau, có nghĩa là xâu này được tạo thành từ các ký tự giống xâu kia và ngược lại. Em hãy giúp bạn An trả lời câu đố trên nhé!
Yêu cầu: Cho trước hai xâu ký tự chỉ gồm các ký tự Latinh in thường từ ‘a’ đến ‘z’ (độ dài d mỗi xâu không quá 50000) hãy tính tổng số lượng ký tự ít nhất cần xóa (ở cả hai xâu) để nhận được hai xâu có ký tự giống nhau.
Dữ liệu: Đọc từ tệp văn bản ERASE.INP gồm:
Kết quả: Ghi ra tệp văn bản ERASE.OUT một số nguyên duy nhất là số lượng ký tự ít nhất cần xóa để nhận được hai xâu có ký tự giống. Dữ liệu đảm bảo luôn tìm được một phương án xóa thỏa mãn đề bài.
|
ERASE.INP |
ERASE.OUT |
|
kythihocsinhgioilopchin |
12 |
|
thanhcongtotdep |
(Giải thích: Xóa 9 ký tự lần lượt là k, y, i, s, i, i, i, l, i ở |
|
|
xâu 𝑆1, xóa 3 ký tự lần lượt là a, d, e ở xâu 𝑆2, ta được |
|
|
hai xâu có ký tự giống nhau) |
Ràng buộc: