• 微软原版系统

  • 一键重装系统

  • 纯净系统

  • 在线技术客服

魔法猪系统重装大师 一键在线制作启动 U 盘 PE 系统 用一键重装的魔法拯救失去灵魂的系统
当前位置:首页 > 教程 > 电脑教程

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

时间:2015年04月02日 15:21:09    来源:魔法猪系统重装大师官网    人气:10402

问题描述:

给定两个字符串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;   
}

解法二用空间换取了大量的计算时间。只需要一次匹配即可得到结果。

字符串,移位,包含,的,问,题的,解决方案,问题,
栏目:电脑教程 阅读:1000 2023/12/27
Win7教程 更多>>
U盘教程 更多>>
Win10教程 更多>>
魔法猪学院 更多>>

Copyright © 2015-2023 魔法猪 魔法猪系统重装大师

本站发布的系统仅为个人学习测试使用,请在下载后24小时内删除,不得用于任何商业用途,否则后果自负,请支持购买微软正版软件。

在线客服 查看微信 返回顶部