字符串移位包含的问题的解决方案字符串移位包含的问题的解决方案
问题描述:
给定两个字符串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);...
字符串移位包含的问
的解决
问题描述:
给定两个字符串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;
}
解法二用空间换取了大量的计算时间。只需要一次匹配即可得到结果。
推荐阅读:java培训 3g培训 C++培训 南宁达内java培训:www.nntarena.com
本文档为【字符串移位包含的问题的解决方案】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。