Algorithmen und Datenstrukturen

Äquivalente Zeichenketten

Wir führen eine neue Definition der Äquivalenz (​~) von Zeichenketten ein. Zwei Zeichenketten a und b gelten dann als äquivalent, wenn sie die gleiche Länge haben und einer der folgenden Fälle erfüllt ist:
  1. a ist mit b identisch (a == b)
  1. Falls man a in zwei gleich lange Teile a1 und a2 aufteilt und b in zwei gleich lange Teile b1 und b2, dann gilt:
    1. a1 ist äquivalent zu b1, und a2 ist äquivalent zu b2 (a1 ~ b1 und a2 ~ b2)
    2. a1 ist äquivalent zu b2, und a2 ist äquivalent zu b1 (a1 ~ b2 und a2 ~ b1)
Sind zwei Zeichenketten a und b gegeben, so soll man bestimmen, ob diese beiden Zeichenketten äquivalent sind.

Eingabe

In der ersten Zeile der Eingabe steht die Zeichenkette a (1 ≤ |a| ≤ ).
In der zweiten Zeile der Eingabe steht die Zeichenkette b (1 ≤ |b| ≤ ).
Die Längen |a| und |b| sind jeweils eine Zweierpotenz.

Ausgabe

Das Programm soll Yes ausgeben, wenn a äquivalent zu b ist, andernfalls No.

Beispiele

Input
Output
bbcb bcbb
Yes
bbaa baba
No

Erklärung

  1. bbcb → bb + cb, bcbb → bc + bb ⇒ bb ist äquivalent zu bb; außerdem ist cb äquivalent zu bc, da wir cb → c + b und bc → b + c aufteilen können ⇒ diese sind äquivalent.
  1. bbaa → bb + aa, baba → ba + ba ⇒ es gibt keine passenden Paare, da man bei weiterer Aufteilung aa mit einer der ba-Zeichenketten vergleichen müsste und in aa keine b-Zeichen vorhanden sind. Folglich sind sie nicht äquivalent.
 

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