分数: 800 点
问题陈述
给你字符串 s 和 t 长度 N 组成 0 和 1。
判断是否可以制作 s 匹配 t 至少执行以下操作 0 最多 N+1 次,如果可能的话,显示一个这样的操作序列。
操作:按顺序执行以下操作。
- 选择整数 a 和 b 满意 1 \le a,b \le N 和 |a-b|=1
- 附加 a- 从开头算起的第一个字符 s 到年底 s
- 删除 b- 从开头算起的第一个字符 s 并按原始顺序连接其余字符
你被给予 T 测试用例;为他们每个人找到答案。
约束
- 1 \le T \le 10^{5}
- 2 \le N \le 2 \times 10^{5}
- s 和 t 是长度的字符串 N 组成
0和1. - 总和 N 所有测试用例最多 2 \times 10^{5}.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N s t
输出
按照给出的顺序打印给定测试用例的答案。
如果无法制作 s 匹配 t 通过至少执行操作 0 最多 N+1 次,打印 -1。
如果可能的话,首先打印操作次数 K,并在 j- 以下各项 K 行,打印两个整数 a_j 和 b_j 选择于 j第一个操作,以空格分隔。
示例输入 1
3 5 00101 00010 2 01 01 2 00 11
示例输出 1
1 2 3 0 -1
在第一个测试用例中, s is 00101 和 t is 00010.
- 通过选择 2 和 3 as a 和 b,附加 2-nd 字符
0到年底 s,然后删除 3-rd 字符,我们可以制作 s 和 t 匹配。 - 请注意,整数 a 和 b 在操作中选择必须满足 |a-b|=1.
在第二个测试用例中, s 和 t 可以与零运算相匹配。
在第三个测试用例中,无论如何执行操作, s 和 t 无法匹配。