等价类

喜串的定义:字符串 a 与字符串 b 互为喜串需满足以下两个条件之一:

a 和 b 相同。
将 a 分成 a1 与 a2 两个等长串，b 分成 b1 与 b2 两个等长串，其子串需满足以下两个条件之一:

a1 与 b1 互为喜串且 a2 与 b2 互为喜串。a1 与 b2 互为喜串且 a2 与 b1 互为喜串。

1.暴力，T(n)=4T(n/2)+O(n)
2.喜串是等价，a1 = b1, a2 = b2, a1 = b2, a2 = b1 不可能出现3T1F的情况，不需要四次判断

T(n)=3T(n/2)+O(n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[(1<<18)+1], b[(1<<18)+1];
bool isEqual(int l1, int l2, int len)
{
    int lim = l1 + len;
    for(; l1 < lim; l1++, l2++)
        if(a[l1] != b[l2])
            return false;
    return true;
}
bool check(int l1, int l2, int len)
{
    if(isEqual(l1, l2, len)) return true;
    if(len & 1) return false;
    if(check(l1, l2 + len / 2, len / 2))
    {
        if(check(l1 + len / 2, l2, len / 2)) return true;
        return false;
    }
    if(check(l1, l2, len / 2) && check(l1 + len / 2, l2 + len / 2, len / 2))
return true;
    return false;
}
int main() {
    scanf("%s %s", a, b);
    int len = strlen(a);
    if(check(0, 0, len)) printf("Yes
");
    else printf("No
");
}

3.可以找当前等价类里最小的那一个元素进行比较来判断这两个元素在不在同一个等价类

T(n)=2T(n/2)+O(n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[(1<<18)+1], b[(1<<18)+1];
bool isEqual(int len)
{
    for(int i = 0; i < len; i++)
        if(a[i] != b[i])
            return false;
    return true;
}
void Sort(int L, int R, int len, char* a)
{
    if(!(len & 1))
    {
        Sort(L, L + len / 2, len / 2, a);
        Sort(R, R + len / 2, len / 2, a);
    }
    int p = 0;
    while(p < len && a[L+p] == a[R+p]) p++;
    if(p < len && a[L+p] > a[R+p])
    {
        while(p < len)
        {
            swap(a[L+p], a[R+p]);
p++; }
int main() {
    scanf("%s %s", a, b);
    int len = strlen(a);
    if(!(len & 1))
    {
        Sort(0, len / 2, len / 2, a);
        Sort(0, len / 2, len / 2, b);
    }
    if(isEqual(len)) printf("Yes
");
    else printf("No
");
}