Công ty kinh doanh đá quý DQ có 26 loại đá quý khác nhau. Mỗi loại được kí hiệu bằng một chữ cái viết hoa trong bảng chữ cái tiếng Anh. Từ các loại đá trên người ta tạo ra các chuỗi đá quý khác nhau và lưu cấu trúc của chúng vào máy tính. Vì mỗi chuỗi có thể rất dài nên để tiết kiệm không gian lưu trữ người ta nén chuỗi như sau:

- Đọc lần lượt các kí tự trong chuỗi từ trái sang phải, nếu xâu con \(x\) có độ dài \(m\) xuất hiện liên tiếp \(k\) lần trong chuỗi thì thay bằng 3 giá trị: \(m,\ x,\ k\).

Ví dụ: chuỗi MMPNQPNQABABM có thể nén lại như sau:

4 1 M 2 3 PNQ 2 2 AB 2 1 M 1

Khi đọc lần lượt các kí tự từ trái sang phải: chuỗi gồm 4 đoạn, đoạn có độ dài 1 là M lặp lại 2 lần, đoạn có độ dài 3 là PNQ lặp lại 2 lần, đoạn có độ dài 2 là AB lặp lại 2 lần, đoạn có độ dài 1 là M lặp lại 1 lần.

Vì chuỗi hạt hình tròn nên có thể bắt đầu từ một vị trí bất kì theo hướng bất kì. Ta có thể có nhiều cách ghi khác nhau đối với mỗi chuỗi. Chuỗi trên cũng có thể được viết là MMMBABAQNPQNP và được nén như sau: 3 1 M 3 2 BA 2 3 QNP 2

Yêu cầu: Cho 2 dòng mô tả chuỗi đá quý đã được nén. Kiểm tra 2 dòng này có mô tả cùng một chuỗi hay không?

Dữ liệu vào:

+ Gồm 2 dòng, mỗi dòng là mô tả về một chuỗi đá quý đã nén. Các phần trên 1 dòng cách nhau bởi 1 dấu cách, dữ liệu vào đảm bảo chiều dài của chuỗi ban đầu không quá 10⁴ kí tự.

Kết quả:

+ Dòng 1: ghi xâu kí tự ‘CO’ nếu hai dòng mô tả cùng một chuỗi đá quý, ngược lại thì ghi xâu kí tự ‘KHONG’.

+ Dòng 2: đưa ra độ dài của 2 chuỗi sau khi đã giải nén theo thứ tự đọc vào, mỗi số cách nhau 1 dấu cách.

Ví dụ: