Xâu tương đương
Đề bài
Mô tả
Cho hai xâu và có độ dài bằng nhau. Ta định nghĩa hai xâu có cùng độ dài là tương đương nếu thỏa mãn một trong hai điều kiện sau:
- Hai xâu bằng nhau.
- Nếu độ dài của chúng là số chẵn, ta chia xâu thành hai nửa bằng nhau và xâu thành hai nửa bằng nhau . Khi đó hai xâu tương đương nếu xảy ra một trong hai trường hợp:
- tương đương với và tương đương với ;
- tương đương với và tương đương với .
Hãy xác định hai xâu đã cho có tương đương hay không.
Dữ liệu vào
- Dòng thứ nhất chứa xâu .
- Dòng thứ hai chứa xâu .
Mỗi xâu gồm các chữ cái Latin thường và hai xâu có cùng độ dài.
Dữ liệu ra
In ra YES nếu hai xâu tương đương, ngược lại in ra NO.
Ràng buộc
- .
- Các xâu chỉ gồm chữ cái Latin thường.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| aabb abab |
NO | Xâu aabb được tách thành aa và bb, cả hai chỉ tương đương với chính nó, nên aabb chỉ tương đương với chính nó và với bbaa. Do đó aabb không tương đương abab. |
| aaba abaa |
YES | Tách aaba thành aa, ba và abaa thành ab, aa. Ta có aa tương đương aa; còn ab tương đương ba vì ab = a+b, ba = b+a nên đổi chỗ hai nửa cho nhau. |
Bình luận