Thay thế ký tự
Xem dạng PDFMô tả và yêu cầu
Cho hai xâu ký tự s và t đều có n ký tự là các chữ cái tiếng Anh in thường.
Người ta muốn thay thế các ký tự trong hai xâu để chúng giống hệt nhau. Với một
phép biến đổi, ta có thể thay đổi một số chữ cái trên 2 xâu. Bạn hãy tính toán số phép
biến đổi tối thiểu để hoàn thành việc này.
Chính xác là, Bạn sử dụng các phép biến đổi dạng R(c1, c2) (trong đó c1 và c2
là các chữ cái). Bạn có thể thực hiện một phép biến đổi nào đó với số lần tùy ý để
biến đổi một chữ cái c1 thành một chữ cái c2 và ngược lại trên cả hai hai xâu s và t.
Bạn cần tìm số phép biến đổi tối thiểu để cho s và t giống hệt nhau. Thêm nữa, bạn
cần in ra chi tiết về các phép biến đổi đó. Xem ví dụ để rõ hơn.
Dữ liệu
Dòng đầu chứa số nguyên n (1 ≤ n ≤ 105) là độ dài các xâu ký tự.
Dòng thứ hai chứa n chữ cái tiếng Anh in thường , mô tả xâu s.
Dòng thứ ba chứa n chữ cái tiếng Anh in thường, mô tả xâu t.
Dữ liệu ra
Dòng đầu in ra số nguyên k là tổng số phép biến đổi tối thiếu cần thực hiện
Trong k dòng tiếp theo, mỗi dòng in ra một cặp ký tự c1, c2 cách nhau một dấu
cách để mô tả về một phép biến đổi. Các cặp này có thể in theo trật tự bất kỳ. Chú
ý, các phép biến đổi có thể không phải duy nhất.
Ví dụ
INPUT OUTPUT INPUT OUTPUT
3 2 8 7
abb a d drpepper l e
dad b a cocacola e d
d c
c p
p o
o r
r a
Bình luận