思维,递归

题意:

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";
}