思维，递归

题意：

Cgg特别喜欢收集特别的字符串。这天，lfgg给了cgg两个字符串，字符串A，字符串B，声称这是一对神奇的字符串，他们满足如下两个条件的其中之一：
1、 A与B相等。
2、 如果我们把字符串A分成两个长度相等的字符串A1,A2，并将字符串B分成两个长度相等的字符串B1,B2 然后他们满足以下的其中一项条件：
（1） A1与B1是一对神奇的字符串，并且A2与B2是一对神奇的字符串。
（2） A2与B1是一对神奇的字符串，并且A1与B2是一对神奇的字符串。
Lfgg确信他找到了一对神奇字符串，cgg却并不相信。
希望你能帮帮cgg判断，这对字符串是否是一对神奇字符串。

Input
一共两行，一对字符串。
字符串长度为1到200000且仅包含小写英文字母，保证两个字符串长度一致。

Output
如果这是一对神奇字符串，输出“YES”（不含引号）。否则，输出“NO”（不含引号）。

Examples
Input
aaba
abaa
Output
YES
Input
aabb
abab
Output
NO
Note
在第一组样例中，将第一个字符串拆成aa，ba，将第二个字符串拆成ab，aa，显然aa与aa是一对神奇字符串，ba与ab是一对神奇字符串，因为ba与ab可以被拆分成b，a与a，b。

分析

我们的第一反应肯定是递归搜索，直接暴力做了他！
但是，真的能行吗？
代码如下：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string s1;
string s2;

bool solve(int l1,int r1,int l2,int r2) {
    if ( (r1 - l1) == 0)return true;
    int i;
    for (i = 0;i < r1 - l1;i++)
        if (s1[i + l1] != s2[i + l2])break;
    if (i == r1 - l1)return true;
    if ((r1 - l1) & 1)return false;
    int mid1 = (l1 + r1) >> 1;
    int mid2 = (l2 + r2) >> 1;
    if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true;
    if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> s1 >> s2;
    if (solve(0,s1.size(),0,s2.size()))cout << "YES\n";
    else cout << "NO\n";
}

其实当我们看到

if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true;
if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true;

时就已经感到有点不妙了。。
每一次处理下去，所需处理的数据量都需要加倍！！！！！！
（可以画个递归树看看）
这会导致我们的数据处理时间复杂度向O(n^2)方向靠拢！！！！
所以这是不行的！！！！！！

下面是正确的思路

我们再次回顾一下我们需要解决的问题：
我们需要知道字符串s1与字符串s2是否等价！
等价有一些十分重要的性质：传递性，反身性，等价性
这里我们利用传递性！
如果字符串s1等价于字符串s3且字符串s2等价于字符串s3那么字符串s1等价于字符串s3
按照这个性质我们可以确定，对于等价的s1与s2，他们一定身处在同一个等价字符串集合中！！！！
那么我们求等价于字符串s1的最小的字符串ss1，求等价与s2的最小字符串ss2
我们看一看ss1是否相等于ss2，就ok了！！！！！

下面给出代码，注意细节

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string s1;
string s2;

bool solve(int l1,int r1,int l2,int r2) {
    if ( (r1 - l1) == 0)return true;
    int i;
    for (i = 0;i < r1 - l1;i++)
        if (s1[i + l1] != s2[i + l2])break;
    if (i == r1 - l1)return true;
    if ((r1 - l1) & 1)return false;
    int mid1 = (l1 + r1) >> 1;
    int mid2 = (l2 + r2) >> 1;
    if (solve(l1, mid1, l2, mid2) && solve(mid1, r1, mid2, r2))return true;
    if (solve(l1, mid1, mid2, r2) && solve(mid1, r1, l2, mid2))return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> s1 >> s2;
    if (solve(0,s1.size(),0,s2.size()))cout << "YES\n";
    else cout << "NO\n";
}