等価な文字列
新しい文字列の等価性(~)を定義しましょう。2つの文字列 a と b が等価であるとは、両方の文字列が同じ長さを持ち、以下の条件のいずれかを満たす場合をいいます。
aがbと完全に同じである(a == b)もし
aを等しい長さの文字列a1とa2に分割し、同様にbをb1とb2に分割したとき、次のいずれかが成り立つ場合:a1がb1と等価、かつa2がb2と等価(a1 ~ b1およびa2 ~ b2)a1がb2と等価、かつa2がb1と等価(a1 ~ b2およびa2 ~ b1)
2つの文字列 a と b が与えられたとき、これらが等価であるかどうかを調べてください。
Input
最初の行に文字列 a (1 ≤ |a| ≤ ) が与えられます。
次の行に文字列 b (1 ≤ |b| ≤ ) が与えられます。
文字列の長さ |a| と |b| は、それぞれ 2 の冪乗になっています。
Output
もし a が b と等価ならば Yes を、そうでなければ No を出力してください。
Examples
入力例 | 出力例 |
|---|---|
bbcb | Yes |
bbaa | No |
Explanation
bbcb→bb+cb,bcbb→bc+bb⇒bbはbbと等価。一方でcbとbcは、cb→c+b、bc→b+cのように分割すると等価になる。bbaa→bb+aa,baba→ba+ba⇒ ここでペアをさらに分割して比べようとしても、aaをbaと比較することになり、aaにはbが含まれないため、これらの文字列は等価にはならない。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB