2147. 字符环

单点时限: 2.0 sec

内存限制: 256 MB

字符环 : 就是将给定的一个字符串,首尾相连而形成的一个环。

现在我们来玩一个有趣的两人游戏 :

每次甲给出两个字符串 A 和 B, 然后让乙判断字符串 B 是否能够被字符环 A 所包含。
例如 ,A = aabcd,B = cdaa,那么 B 可以包含在 A 经过旋转后的字符串 A’ = cdaab 中。

输入格式

输入数据的第一行,一个正整数 N, 表示测试数据的组数。
对于每个数据 :

首先 2 个正整数 lengtha 和 lengthb 代表字符串 A 和字符串 B 的长度。

接下来一行有两个被一个空格隔开的字符串 A 和 B,A 和 B 的长度如上所输入的长度。

长度的范围是 1<=length<=100,并且字符串种只含有小写字母

输出格式

对于每组测试数据,输出只有一行

如果 B 字符串含在字符环 A 中,则输出:YES 否则输出:NO

样例

Input
2
5 4
aabcd cdaa
5 4
babcd cdaa
Output
YES
NO
Hint:
aabcd 经过顺时针循环移动可以得到:aabcd-->abcda-->bcdaa-->abcda-->cdaab-->daabc
babcd 经过顺时针循环移动可以得到:babcd-->abcdb-->bcdba-->cdbab-->dbabc-->babcd

176 人解决,244 人已尝试。

239 份提交通过,共有 1031 份提交。

3.4 EMB 奖励。

创建: 16 年,4 月前.

修改: 7 年,1 月前.

最后提交: 1 周,6 天前.

来源: 第一届程序设计竞赛