#P0828. 密钥重组
密钥重组
题目描述
霓虹在远方破碎成条,雷鸣像被压低的鼓点。你蜷缩在被遗弃的前哨站地下室里,只剩一盏应急灯和一台老旧便携终端。你点亮最后一枚战术灯——屏幕上跳动的是一串看似无意义的代码。但你知道,这并非普通的杂讯,而是敌军用来掩护关键指令的“活体谜题”。情报中心发来最后一条语音:这串数据里藏着一枚关键暗号,握住它就能截断敌军的命令链,扭转前线局势,成败......在此一举......
在一次秘密任务中,你截获了一段敌方的加密数据串 。
情报部门确认,这段数据中隐藏着一段关键暗号,只要找到它,就能解开敌军的通信协议。
不过,这段加密数据被设计成不断扰乱顺序。你只能通过两种“破解手段”来操作这段数据:
- 操作 - 镜像反转:你可以将整段数据镜像翻转。即将变成。
- 操作 - 轮转切换: 你可以选择一个位置,将前(包括)的子串和后的子串互换位置。即将 变成 $s[pos + 1], s[pos + 2], ..., s[n - 1], s[0], s[1], ..., s[pos]$。
你的任务是:通过最少的操作次数,让目标暗号 出现在数据串 中。
成功破解后,你将获得敌军的秘密指令!
输入格式
本题包含多组测试数据。
第一行为一个整数,测试数据组数。
对于每组测试数据,第一行为两个整数,为两个字符串的长度。
第三行为一个字符串:加密数据串。
第四行为一个字符串:你要找的关键暗号串。
数据保证:和中仅包含小写字母。
输出格式
对于每组测试数据,输出一行一个整数,如果能找到,输出操作的最小次数;如果找不到,输出。
样例
3
6 2
aaabbb
ab
6 2
aaabbb
ba
6 2
aaabbb
bc
0
1
-1
提示
对于第一组测试数据, 中已经包含,无需操作。
对于第二组测试数据,只需执行一次操作1或在中任选一个位置执行一次操作2,即可。
对于第三组测试数据,无论执行多少次操作,也不能让中出现子串。