一道俩个字符串是否包含的问题
题目描述:假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?比如,如果是下面两个字符串: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; }