UOJ Logo Zijian Online Judge

ZOJ

#27. 等价串

Statistics

黎瑟最近在学习字符串的知识。

如果两个长度相等的串 $a,b$ 满足下面任意一个条件,则它们被称作是等价的:

  1. $a=b$。
  2. 如果我们能把 $a$ 劈成两半 $a1,a2$,把 $b$ 也劈成两半 $b1,b2$ ($|a1|=|a2|=|b1|=|b2|$) 且 $a1$ 与 $b1$ 等价 ,$a2$ 与 $b2$ 等价。
  3. 前提同上,$a1$ 与 $b2$ 等价 ,$a2$ 与 $b1$ 等价。

现在有 $T$ 次询问,每次给出两个串 $a,b$,问它们是否是等价的。

输入格式

第一行一个整数 $T$ 表示数据组数。 接下来每组数据,第一行一个小写字母字符串 $a$ ,第二行一个小写字母字符串 $b$ ($|a|=|b|$)。

输出格式

对于每组数据,如果 $a,b$ 等价输出 YES ,否则输出 NO 。

样例一

input

2
aaba
abaa
aabb
abab

output

YES
NO

样例二

见样例数据下载

限制与约定

对于 $20\texttt{%}$ 的数据,$\sum |a| \le 20$。

对于 $50\texttt{%}$ 的数据,$\sum |a| \le 1000$。

对于 $100\texttt{%}$ 的数据,$\sum |a| \le 3*10^5$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载