Algoritmi e Strutture Dati

Stringhe equivalenti

Presentiamo una nuova definizione di equivalenza di stringhe (~). Due stringhe a e b si considerano equivalenti se hanno la stessa lunghezza e se è vero uno dei seguenti casi:
  1. a è identica a b (a == b)
  1. Se dividiamo a in due sottostringhe di uguale dimensione a1 e a2, e b in due sottostringhe di uguale dimensione b1 e b2, allora:
    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)
Dati due stringhe a e b, il problema consiste nello stabilire se queste due stringhe siano equivalenti.

Input

La prima riga dell’input contiene la stringa a (1 ≤ |a| ≤ ).
La seconda riga dell’input contiene la stringa b (1 ≤ |b| ≤ ).
Entrambe le lunghezze |a| e |b| sono potenze di 2.

Output

Il programma deve stampare Yes se a è equivalente a b, altrimenti deve stampare No.

Esempi

Input
Input
bbcb bcbb
bbcb bcbb
bbaa baba
bbaa baba

Spiegazione

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb è equivalente a bb, mentre cb è equivalente a bc poiché possiamo dividere cb → c + b, e bc → b + c ⇒ risultano equivalenti.
  1. bbaa → bb + aa, baba → ba + ba ⇒ nessuna delle coppie è equivalente perché, se le dividiamo ulteriormente, dovremmo confrontare aa con una delle ba, e poiché aa non contiene alcuna b, le due stringhe non risulteranno equivalenti.
 

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