問題描述：
給定兩個字符串s1和s2，要求判定s2是否能被s1循環(huán)移位（rotate）得到的字符串包含。例如，給定字符串s1=AABCD和s2=CDAA，返回true；給定s1=ABCD和s2=ACBD返回false。
分析：
從問題的描述來看，最直接的方式就是對字符串s1進行循環(huán)移位，再判斷s1是否包含s2. 關于字符串匹配可以使用KMP算法，這不是本問題的中心，因此我們使用庫函數(shù)strstr來匹配。char* strstr(char *haystack, char *needle);如果needle為haystack的子串則返回出現(xiàn)的位置，否則返回NULL。
解法一：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
char a[] = "AABCD";
char b[] = "CDAA";
int i, j, res;
char tmp;
int len = strlen(a);
for(i = 0; i < len; i++)
{
tmp = a[0];
for(j = 0; j < len-1; j++)
{
a[j] = a[j+1];
}
a[len-1] = tmp;
if(strstr(a,b))
{
printf("OK");
return 0;
}
}
printf("NOT OK");
return 0;
}這樣做的時間代價是很高的，如果匹配不到，則總共進行了n-1次循環(huán)移位和匹配。
那么，有沒有其他辦法可以不用窮舉s1每次循環(huán)移位的結果呢？
我們先來觀察以下s1循環(huán)移位后到底是什么樣子？
“AABCD"->"ABCDA"->"BCDAA"->"CDAAB"->"DAABC"
s2=“CDAA”
從上面可以看出來，解法1有很多重復的匹配。例如“CDAA”在匹配到“CD”以后需要循環(huán)移位一次重新匹配“CDA”然后“CDAA”，所以主要時間浪費在了循環(huán)移位s1上。那么一個比較簡單的想法就是如果能讓s2=“CDAA”直接去匹配像“CDAAB”這樣的串就可以了。
如果僅僅是把s1的前面每一位“接”到其末尾，那么“AABCDAABCD”就可以對s2進行直接匹配。事實上，如果length(s2)<=length(s1)的情況下，如果s1s1包含s2，那么其循環(huán)移位的結果也是包含s2的。
解法二：
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
char a[] = "AABCD";
char b[] = "CDAA";
char c[] = "AABCDAABCD"
if(strstr(c,b)!=NULL)
printf("OK");
else
printf("NOT OK");
return 0;
}解法二用空間換取了大量的計算時間。只需要一次匹配即可得到結果。
喜歡 
頂
難過
囧
圍觀
無聊
