Algorithmes et Structures de Données

Chaînes équivalentes

Nous allons introduire une nouvelle définition de l’équivalence entre chaînes (~). Deux chaînes a et b sont considérées équivalentes si elles ont la même longueur et que l’une des conditions suivantes est remplie :
  1. a est identique à b (a == b)
  1. Si nous partageons a en deux sous-chaînes de même taille a1 et a2, et b en deux sous-chaînes de même taille b1 et b2, alors :
    1. a1 est équivalente à b1, et a2 est équivalente à b2 (a1 ~ b1 et a2 ~ b2)
    2. a1 est équivalente à b2, et a2 est équivalente à b1 (a1 ~ b2 et a2 ~ b1)
Étant donné deux chaînes a et b, vous devez déterminer si ces deux chaînes sont équivalentes.

Entrée

La première ligne de l’entrée contient la chaîne a (1 ≤ |a| ≤ ).
La deuxième ligne de l’entrée contient la chaîne b (1 ≤ |b| ≤ ).
Les deux longueurs |a| et |b| sont des puissances de 2.

Sortie

Le programme doit afficher Yes si a est équivalente à b, et No sinon.

Exemples

Entrée
Sortie
bbcb bcbb
Yes
bbaa baba
No

Explication

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb est équivalente à bb, tandis que cb est équivalente à bc puisqu’on peut diviser cb → c + b et bc → b + c ⇒ elles sont donc équivalentes.
  1. bbaa → bb + aa, baba → ba + ba ⇒ aucune paire n’est équivalente, car si l’on continue de diviser, il faudrait comparer aa à l’une des ba, et du fait qu’il n’y a pas de caractère b dans aa, ces chaînes ne seront pas équivalentes.
 

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