比如说给定字符串“ABCD"通过循环移位是否可以包含“CDAB”。

有两种方法，一种方法就是通过创建另外一个字符串，这个字符串是两个“ABCD”的连接，然后应用kmp在新创建的字符串中查找"CDAB"，这样的时间复杂度是O（n）， 空间复杂度也是O（n），还有另外一种方法是可在O（n）时间内完成，下面给出代码：

1. #include<iostream>  
2. #include<string>  
3. #include<stdio.h>  
4. using namespace std;  
5.   
6. void getNext(char* pattern, int length, int* next) {  
7.     int i = 0;  
8.     int j = -1;  
9.     next[i] = -1;  
10.     while (i < length - 1) {  
11.         if (-1 == j || pattern[j] == pattern[i]) {  
12.             ++i;  
13.             ++j;  
14.             if (pattern[i] == pattern[j]) {  
15.                 next[i] = next[j];  
16.             } else {  
17.                 next[i] = j;  
18.             }  
19.         } else {  
20.             j = next[j];  
21.         }  
22.     }  
23. }  
24.   
25. char* kmpSearch(char* source, char* pattern) {  
26.     int src_len = strlen(source);  
27.     int pat_len = strlen(pattern);  
28.     int i, j;  
29.     int* next = new int[pat_len];  
30.     for (i = 0; i < pat_len; i++)  
31.         next[i] = 0;  
32.     getNext(pattern, pat_len, next);  
33.     j = -1;  
34.     i = 0;  
35.     while (i < src_len && j < pat_len) {  
36.         if (-1 == j || source[i] == pattern[j]) {  
37.             ++i;  
38.             ++j;  
39.         } else {  
40.             j = next[j];  
41.         }  
42.     }  
43.     delete []next;  
44.     if (j >= pat_len)  
45.         return source + i - pat_len;  
46.     return NULL;  
47. }  
48.   
49. bool isContainReverse(char* src, char* dst) {  
50.     int src_len = strlen(src);  
51.     int dst_len = strlen(dst);  
52.     if (dst_len > src_len)  
53.         return false;  
54.     char* temp = new char[src_len * 2 + 1];  
55.     sprintf(temp, "%s%s", src, src);  
56.     bool rst = kmpSearch(temp, dst);  
57.     delete []temp;  
58.     return rst;  
59. }  
60.   
61. bool isReverseContain(char* src, char* dst) {  
62.     int dst_contain_count = 0;  
63.     int src_contain_count = 0;  
64.     int src_len = strlen(src);  
65.     int dst_len = strlen(dst);  
66.     char ch = *dst;  
67.     char* p = dst;  
68.     while (*p) {  
69.         if (ch != *p)  
70.             break;  
71.         dst_contain_count++;  
72.         p++;  
73.     }  
74.     p = strchr(src, ch);  
75.     while (p) {  
76.         char* temp = p;  
77.         src_contain_count = 0;  
78.         while (*p) {  
79.             if (ch != *p)  
80.                 break;  
81.             src_contain_count++;  
82.             p++;  
83.         }  
84.         p = strchr(p, ch);  
85.         if (src_contain_count < dst_contain_count)  
86.             continue;  
87.         int i = temp - src + src_contain_count - dst_contain_count;  
88.         int j = 0;  
89.         while (j < dst_len) {  
90.             if (src[i] != dst[j]) {  
91.                 break;  
92.             }  
93.             i = (i + 1) % src_len;  
94.             j += 1;  
95.         }  
96.         if (j >= dst_len)  
97.             return true;  
98.     }  
99.     return false;  
100. }  
101.   
102. int main(int argc, char* argv[]) {  
103.     char src[] = "passportpasssportsssssport";  
104.     char dst[] = "sssssportpassportpasssport";  
105.     bool rst = isReverseContain(src, dst);  
106.     if (rst)  
107.         cout << "yes" << endl;  
108.     else  
109.         cout << "non" << endl;  
110.     cin.get();  
111.     return 0;  
112. }