trang chủ / bài tập / equivstr

Xâu tương đương

Đề bài

Mô tả

Cho hai xâu ab 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:

  1. Hai xâu bằng nhau.
  2. Nếu độ dài của chúng là số chẵn, ta chia xâu a thành hai nửa bằng nhau a1,a2 và xâu b thành hai nửa bằng nhau b1,b2. Khi đó hai xâu tương đương nếu xảy ra một trong hai trường hợp:
    • a1 tương đương với b1 a2 tương đương với b2;
    • a1 tương đương với b2 a2 tương đương với b1.

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 a.
  • Dòng thứ hai chứa xâu b.

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

  • 1|a|=|b|2·105.
  • 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0