Algoritmos y Estructuras de Datos

Cadenas equivalentes

Empecemos con una nueva definición de equivalencia de cadenas (~). Dos cadenas a y b son equivalentes si tienen la misma longitud y se cumple uno de los siguientes casos:
  1. a es idéntica a b (a == b)
  1. Si dividimos a en dos cadenas del mismo tamaño, a1 y a2, y a su vez dividimos b en otras dos cadenas del mismo tamaño, b1 y b2, entonces:
    1. a1 es equivalente a b1, y a2 es equivalente a b2 (a1 ~ b1 y a2 ~ b2)
    2. a1 es equivalente a b2, y a2 es equivalente a b1 (a1 ~ b2 y a2 ~ b1)
Dadas dos cadenas a y b, se te pide determinar si dichas cadenas son equivalentes.

Entrada

La primera línea de la entrada contiene la cadena a (1 ≤ |a| ≤ ).
La segunda línea de la entrada contiene la cadena b (1 ≤ |b| ≤ ).
Las longitudes |a| y |b| son potencias de 2.

Salida

El programa debe imprimir Yes si a es equivalente a b, y No en caso contrario.

Ejemplos

Entrada
Salida
bbcb bcbb
Yes
bbaa baba
No

Explicación

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb es equivalente a bb, mientras que cb es equivalente a bc, pues podemos dividir cb → c + b, y bc → b + c ⇒ son equivalentes.
  1. bbaa → bb + aa, baba → ba + ba ⇒ no hay pares equivalentes, porque si las dividimos aún más, tendríamos que comparar aa con cualquiera de las ba, y como aa no contiene ninguna b, las dos cadenas no serán 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