[ybtoj advanced training guide] similar string [string] [simulation]

Ideas ：

Because similarity is transitive , You can directly recursively judge

$code$

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int t;

bool campare_(char *s1, char *s2, int len)
{
    
	for(int i=0; i<len; i++)
		if(s1[i]>s2[i])
			return 1;
		else if(s1[i]<s2[i])
			return 0;
	return 0;
}

bool check(char *s1, char *s2, int len)
{
    
// cout<<s1<<' '<<s2<<endl;
	for(int j=0; j<len; j++)
		if(s1[j]!=s2[j])
		{
    
			if(len&1)
				return 0;
			int slen=len/2;
			char a[slen+10], b[slen+10], c[slen+10], d[slen+10];
			for(int i=0; i<slen; i++)
				a[i]=s1[i], c[i]=s2[i];
			for(int i=slen; i<len; i++)
				b[i-slen]=s1[i], d[i-slen]=s2[i];
			if(campare_(a, b, slen))
				for(int i=0; i<slen; i++)
					swap(a[i], b[i]);
			if(campare_(c, d, slen))
				for(int i=0; i<slen; i++)
					swap(c[i], d[i]);
			return (check(a, c, slen)&&check(b, d, slen))||(check(a, d, slen)&&(check(b, c, slen)));
		}
	return 1;
}

int main()
{
    
	scanf("%d ", &t);
	while(t--)
	{
    
		char s[500010], ss[500010];
		scanf("%s", s);
		scanf("%s", ss);
		if(check(s, ss, strlen(s)))
			printf("YES\n");
		else printf("NO\n");
	} 
	return 0;
}
/* ccfnzfnw wnfzccnf */