首页 > 代码库 > [转] 编程之美--字符串移位包含的问题

[转] 编程之美--字符串移位包含的问题

问题描述

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

解法一:

 1 #include <stdio.h> 2  #include <stdlib.h> 3  #include <string.h> 4  5 int main(void) 6 { 7      char a[] = "AABCD"; 8      char b[] = "CDAA"; 9  10      int i, j, res;11      char tmp;12      int len = strlen(a);13  14      for(i = 0; i < len; i++)15      {16          tmp = a[0];17          for(j = 0; j < len-1; j++)18         {19              a[j] = a[j+1];20           }21          a[len-1] = tmp;22  23          if(strstr(a,b))24           {25              printf("OK");26              return 0;27          }28      }29      printf("NOT OK");30  31      return 0;32 }

这样做的时间代价是很高的,如果匹配不到,则总共进行了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的。

 

解法二:

 1 #include<stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4  5 int main(void) 6 { 7   char a[] = "AABCD"; 8   char b[] = "CDAA"; 9   char c[] = "AABCDAABCD"10   if(strstr(c,b)!=NULL)11      printf("OK");12   else13      printf("NOT OK");14    return 0;   15 }

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

 

以上内容转自:http://www.cnblogs.com/bigwangdi/archive/2013/05/23/3095507.html