读书人

一道俩个字符串是否包含的有关问题

发布时间: 2012-11-22 00:16:41 作者: rapoo

一道俩个字符串是否包含的问题
题目描述:假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?比如,如果是下面两个字符串:String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPOM答案是true,所有在string2里的字母string1也都有。如果是下面两个字符串: String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPOZ 答案是false,因为第二个字符串里的Z字母不在第一个字符串里。

这个问题来自july的博客: http://blog.csdn.net/v_july_v/article/details/6347454#comments

博客中讨论了很多种解法,我在这里给出我的解法。

//copyright@ nossiac  //July、updated,2011.04.24。  #include <stdio.h>  #include <string.h>    #define getbit(x) (1<<(x-'a'))    void a_has_b(char * a, char * b)  {      int i = 0;      int dictionary = 0;      int alen = strlen(a);      int blen = strlen(b);            for(i=0;i<alen;i++)          dictionary |= getbit(a[i]);            for(i=0;i<blen;i++)      {          if(dictionary != (dictionary|getbit(b[i])))              break;      }            if(i==blen)          printf("YES! A has B!/n");      else          printf("NiO!  Char at %d is not found in dictionary!/n",i);  }    int main()  {      char * str1="abcdefghijklmnopqrstuvwxyz";      char * str2="akjsdfasdfiasdflasdfjklffhasdfasdfjklasdfjkasdf";      char * str3="asdffaxcfsf";      char * str4="asdfai";            a_has_b(str1, str2);      a_has_b(str1, str3);      a_has_b(str3, str4);            return 0;  }  



读书人网 >编程

热点推荐