字符串移位包含的问题的解决方案

欢迎您访问我爱IT技术网，今天小编为你分享的操作系统知识是：【字符串移位包含的问题的解决方案 】，下面是详细的分享！

字符串移位包含的问题的解决方案

问题描述：

给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD返回false。

分析：

从问题的描述来看，最直接的方式就是对字符串s1进行循环移位，再判断s1是否包含s2. 关于字符串匹配可以使用KMP算法，这不是本问题的中心，因此我们使用库函数strstr来匹配。char* strstr(char *haystack, char *needle);如果needle为haystack的子串则返回出现的位置，否则返回NULL。

解法一：

#include
#include
#include

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次循环移位和匹配。

那么，有没有其他办法可以不用穷举s1每次循环移位的结果呢？

我们先来观察以下s1循环移位后到底是什么样子？

“AABCD"->"ABCDA"->"BCDAA"->"CDAAB"->"DAABC"

s2=“CDAA”

从上面可以看出来，解法1有很多重复的匹配。例如“CDAA”在匹配到“CD”以后需要循环移位一次重新匹配“CDA”然后“CDAA”，所以主要时间浪费在了循环移位s1上。那么一个比较简单的想法就是如果能让s2=“CDAA”直接去匹配像“CDAAB”这样的串就可以了。

如果仅仅是把s1的前面每一位“接”到其末尾，那么“AABCDAABCD”就可以对s2进行直接匹配。事实上，如果length(s2)<=length(s1)的情况下，如果s1s1包含s2，那么其循环移位的结果也是包含s2的。

解法二：

#include

#include
#include

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;
}解法二用空间换取了大量的计算时间。只需要一次匹配即可得到结果。

以上就是关于字符串移位包含的问题的解决方案 的操作系统教程分享，更多操作系统知识请移步到>>操作系统频道。