Алгоритмы и структуры данных

Эквивалентные строки

Давайте введём новое определение эквивалентности строк (~). Две строки a и b считаются эквивалентными, если они имеют одинаковую длину и выполняется одно из двух условий:
  1. a идентична b (a == b).
  1. Если мы разбиваем a на две подстроки одинакового размера a1 и a2, а b — на две подстроки b1 и b2 такого же размера, то справедливо одно из следующих утверждений:
    1. a1 эквивалентна b1, и a2 эквивалентна b2 (a1 ~ b1 и a2 ~ b2),
    2. a1 эквивалентна b2, и a2 эквивалентна b1 (a1 ~ b2 и a2 ~ b1).
Задача: по заданным строкам a и b определить, являются ли они эквивалентными.

Входные данные

Первая строка входа содержит строку a (1 ≤ |a| ≤ ).
Вторая строка входа содержит строку b (1 ≤ |b| ≤ ).
Обе длины |a| и |b| являются степенями двойки.

Выходные данные

Программа должна вывести Yes, если a эквивалентна b, и No в противном случае.

Примеры

Входные данные
Выходные данные
bbcb bcbb
Yes
bbaa baba
No

Пояснение

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb эквивалентна bb, а cb эквивалентна bc, поскольку, разбивая cb → c + b и bc → b + c, мы видим, что они эквивалентны.
  1. bbaa → bb + aa, baba → ba + ba ⇒ ни одна пара не оказываются эквивалентными, потому что при дальнейшем разбиении нам придётся сравнивать aa с одной из ba, и поскольку в aa нет символов b, данные строки не могут быть эквивалентны.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue