XTU OJ 1337 Clockwise Or Unclokwise
题目描述
我们把一个字符串A按圆圈排列，你可以从圆圈上任意一个字符开始，顺时钟或者逆时钟读若干个字符，请问是否能得到给定的字符串B？比如字符串A="abcde"，我们从第2个字符开始，逆时钟读3个字符，可以得到字符串"bae"。
输入
第一行是样例数T(1≤T≤100)。 每个样例的占两行，第一行是字符串A，第二行是字符串B，所有字符串都只含小写英文字母，且长度不超过100个字符。
输出
每行输出一个样例的结果，如果可以输出"Yes"，否则输出"No"。
样例输入
5 abcde cbae abcde deab abc abcabc abcb babcba ab aa样例输出
Yes Yes Yes Yes No
快要期末考试了，重新复习谢大OJ时有了一些不同的思路，发出来和同学们一起探讨
解题思路：破环成链 + 字符串匹配;
当我们遇到一个环，例如一个三角形abc,那么我们添加一个链ABCABC，你就会发现，这个环上能读到的字母在这个链上也能读到，所以我们这道题就可以转化成链来进行字符串匹配。
这个题有特殊的点是子串长度可能比原字符串要长，例如样例abc和abcabc，所以我们不能只扩一倍，我们可以把这个链扩到200。
AC代码:
#include <stdio.h>
#include <string.h>char str[210];
char p[101];
char temp[101];int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",temp);//读取字符串scanf("%s",p);//读取模板串int lenS = strlen(temp);int lenP = strlen(p);for(int i = 0;i < 201;i++) str[i] = temp[i % lenS];//破环成链int maxLen = 200;//开始匹配 顺时针int isMatch = 0;for(int i = 0,j = 0;i < maxLen;){int t = i;while(str[i] == p[j] && j < lenP){i++;j++;}if(j == lenP){printf("Yes\n");isMatch = 1;break;}else {i = t + 1;j = 0;}}//逆时针if(isMatch == 0){for(int i = maxLen - 1,j = 0;i >= 0;){int t = i;while(str[i] == p[j] && j < lenP){i--;j++;}if(j == lenP){printf("Yes\n");isMatch = 1;break;}else{i = t - 1;j = 0;}}}if(isMatch == 0) printf("No\n");}return 0;
}