CF559B Equivalent Strings

题目

题目

思路

注意到这里的等价具有传递性，我们可以求出字典序最小的2个等价串并判断是否相等。
code：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
string x,y;
string f(int l,int r)
{
	if ((r-l+1)%2==1)
	{
		string u="";
		for (;l<=r;l++) u+=x[l];
		return u;
	}
	string ux=f(l,(l+r)>>1),uy=f(((l+r)>>1)+1,r);
	if (ux<uy) return ux+uy;
	else return uy+ux;
}
string f2(int l,int r)
{
	if ((r-l+1)%2==1)
	{
		string u="";
		for (;l<=r;l++) u+=y[l];
		return u;
	}
	string ux=f2(l,(l+r)>>1),uy=f2(((l+r)>>1)+1,r);
	if (ux<uy) return ux+uy;
	else return uy+ux;
}
int main()
{
	cin>>x>>y;
	if (f(0,x.size()-1)==f2(0,y.size()-1))
	{
		cout<<"YES";
	}
	else cout<<"NO";
	return 0;
}