开始: 2026-10-06 00:00:00

【集训04】CSP-J模拟赛1006

结束: 2026-10-07 00:00:00
当前  2026-11-04 11:35:09  类型: IOI  状态: 已经结束 

P6. 等价字符串eq
描述

两个长度相同的字符串 s、t。定义它们的**标准形** f(x) 如下(递归):

其中 + 表示字符串拼接,\min 取字典序较小者。长度为奇数的串无法再平分,递归直接返回自身。

直观地说:偶数长的串可以不断"对半分",在每一个偶数节点上都**允许交换左右两半**;若 s 经过若干次这样的交换能变成 t(即 f(s)=f(t)),就称 s 与 t **等价**。请判断给定的 s、t 是否等价。


输入

第一行一个字符串 s。

第二行一个字符串 t。两串仅含小写字母且长度相同。


输出

等价输出 `YES`,否则输出 `NO`。


样例

输入

aaba
abaa

输出

YES

输入

aabb
baba

输出

NO
提示

样例 1:f(\texttt{aaba}):前一半 `aa` 标准形 `aa`,后一半 `ba` 标准形 `ab`(`b`、`a` 交换取小);两半拼接取小 → `aaab`。f(\texttt{abaa}):前一半 `ab`→`ab`,后一半 `aa`→`aa`,取小仍是 `aaab`。两者相同,等价。样例 2:f(\texttt{aabb})=\texttt{aabb},f(\texttt{baba})=\texttt{abab},不等价。


| 20% | 1~5 | 20 | \lvert s\rvert \le 20 | 

| 60% | 6~15 | 40(累计 60) | \lvert s\rvert \le 2000 | 

| 100% | 16~25 | 40(累计 100) | \lvert s\rvert \le 2 \times 10^5 | 

本题按照数据范围进行捆版测试

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交