字符串-字符串的包含-两种基本思路

/* 2016 9 27 字符串a有"ABCD",字符串b有"BCE",写个函数判断a中是否包含b中所有的元素 返回bool类型 方法一 蛮力轮询 时间复杂度 O(mn) */ #include <stdlib.h> #include <stdio.h> #include <string.h> int ContainString(char *a,char *b) { int i,j; for(i=0;i<strlen(b);i++) { for(j=0;j<strlen(a);j++) { if(b[i]==a[j]) break; if(j==(strlen(a)-1)) return 0; } } return 1; } int main() { char a[]="ABCD"; char b[]="BCD"; printf("strlen(a)=%d\n",strlen(a));/*4*/ printf("sizeof(a)=%d\n",sizeof(a));/*5*/ int tmp=ContainString(a,b); if(tmp) printf("True\n"); else printf("False\n"); } /* 2016 9 27 字符串a有"ABCD",字符串b有"BCE",写个函数判断a中是否包含b中所有的元素 方法二 位运算法 为简单起见,a和b中的元素都为大写 思路 1.将a中的元素在一个26位的数中对应的位置1 2.将b中的元素和a中对应的位比较,若不符合返回false 3.最后返回true 时间复杂度O(m+n) */ #include <stdlib.h> #include <stdio.h> #include <string.h> int ContainString(char *a,char *b) { int hash=0; int i; for(i=0;i<strlen(a);i++) { hash=hash | (1<<(a[i]-'A')); } for(i=0;i<strlen(b);i++) { if((hash & (1<<b[i]-'A'))==0) return 0; } return 1; } int main() { char a[]="ABCDEFGHJIS"; char b[]="BCDA"; printf("strlen(a)=%d\n",strlen(a)); printf("sizeof(a)=%d\n",sizeof(a)); int tmp=ContainString(a,b); if(tmp) printf("True\n"); else printf("False\n"); }