问题描述
给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD返回false。
对问题的两种分析，详见：http://www.cnblogs.com/bigwangdi/archive/2013/05/23/3095507.html
思路一 是暴力算法，穷举所有最后还不一定找到。
思路二 使用空间换取时间，是一种很好的思路。下面给出另外两个思路：
思路三 思路二的优化。增加和源字串产度相同的空间，其实在大部分情况下造成浪费，可以根据待查字串动态分配指定的空间。如图：
代码：
#include <string.h> #include <stdio.h> #include <stdlib.h> int main() { char a[] = "012345"; char b[] = "45012"; int i, j; int lenc = strlen(a) + strlen(b) - 1; char *c = (char*)malloc(sizeof(char) * lenc); strcat(c, a); for(i=0; i<strlen(b)-1; i++) c[strlen(a)+i] = a[i]; printf("%s\n", c); if(strstr(c, b)) printf("Yes!\n"); else printf("No!\n"); free(c); return 0; }
结果： 0123450123
Yes！
思路四
首先看个子问题：
问题描述 平移abc123，是结果为123abc
可以注意旋转平移——浪费时间
可以用备用数组暂存——浪费空间
优化：翻转函数rev()，例如：rev(abc) = cba;
那么rev(abc123) = rev(rev(abc)rev(123)) = rev(cba321)= 123abc
对于原始字串abcdef,旋转后，观察规律(如下)，可以看出如果
fabcde
efabcd
defabc
cdefab
bcdefa
可以看出首尾字符起决定作用，可以根据待查字串找出旋转元素的个数，然后旋转源字串，判断待查字串是否在源字串中。如图：
代码：
#include <stdio.h> #include <string.h> char swap(char *a, int begin, int end) { int i,j; char tmp; for(i=begin,j=end; i<j; i++,j--) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } int main() { char c[] = "abcdef"; char aim[] = "fab"; char *p; int lens; p = strstr(c, aim); if(p) { printf("Yes, it's a part\n"); return 0; } if(strlen(c) < strlen(aim)) { printf("No, it's not a part!\n"); return -1; } if(strlen(c) == 1) { printf("No, it's not a part\n"); return -1; } char token[2] = {c[strlen(c)-1], c[0]}; p = strstr(aim, token); while(p) { lens = p - aim + 1; swap(c, 0, strlen(c)-1-lens); swap(c, strlen(c)-lens, strlen(c)-1); swap(c, 0, strlen(c)-1); if (strstr(c, aim)) { printf("Yes, it is a part\n"); return 0; } p = strstr(p+1, token); //注意其中有诈，有可能之前找到的并不是首尾字串而是其中的一部分。 } printf("No, it's not a part\n"); return 0; }
结果：Yes, it is a part
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/06/01/3105042.html，如需转载请自行联系原作者
