Algoritmos e Estruturas de Dados

Strings Equivalentes

Vamos introduzir uma nova definição de equivalência de strings (~). Duas strings a e b são consideradas equivalentes caso tenham o mesmo tamanho e satisfaçam uma das seguintes condições:
  1. a é idêntica a b (a == b).
  1. Se dividirmos a em duas partes de mesmo tamanho, a1 e a2, e b em b1 e b2, então ocorre uma das situações:
    1. a1 é equivalente a b1 e a2 é equivalente a b2 (a1 ~ b1 e a2 ~ b2).
    2. a1 é equivalente a b2 e a2 é equivalente a b1 (a1 ~ b2 e a2 ~ b1).
Dadas duas strings a e b, deve-se determinar se essas duas strings são equivalentes.

Entrada

A primeira linha da entrada contém a string a (1 ≤ |a| ≤ ).
A segunda linha da entrada contém a string b (1 ≤ |b| ≤ ).
Tanto |a| quanto |b| são potências de 2.

Saída

O programa deve imprimir Yes se a for equivalente a b, ou No caso contrário.

Exemplos

Entrada
Saída
bbcb bcbb
Yes
bbaa baba
No

Explicação

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb é equivalente a bb, enquanto cb é equivalente a bc pois, ao dividirmos cb → c + b e bc → b + c, concluímos que também são equivalentes.
  1. bbaa → bb + aa, baba → ba + ba ⇒ nenhum par é equivalente porque, ao prosseguir com as divisões, é necessário comparar aa com alguma das partes ba, e como não há b em aa, as duas strings não são equivalentes.
 

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