每天一道面试题（二）
（合合信息科技.2013/10/19）给定一长一短的两个字符串A，B，假设A长B短，现在要你判断B是否包含在字符串A中（不区分大小写）。并给出算法计算复杂度和存储复杂度。比如，如果是下面的两个字符串string A：ABCDEFGHLMNOPQRS ，string B:DCGSRQPOM，答案是true。
分析：先明确题意，题目意思指的是短串里出现的字符在长串里都出现过，但是同一类型的字符短串可以比长串多，例如string A:ABC string B:AA且假定空字符可以被任意字符包含
解法一：hash表法
bool IsStringBinStringA(const char *strA,const char *strB){//忽略字符串为空的情况assert(strA!=NULL||strB!=NULL);unsigned index[26]={1,2,4,8,16,32,64,128,256,512,1024,1<<11, 1<<12,1<<13,1<<14,1<<15,1<<16,1<<17,1<<18,1<<19, 1<<20,1<<21,1<<22,1<<23,1<<24,1<<25}; //2的n次幂 unsigned srcdata=0; unsigned desdata=0; while( *strA) *strA>90?srcdata|=index[(*strA++)-'a']:srcdata|=index[(*strA++)-'A']; while(*strB) *strB>90?desdata|=index[(*strB++)-'a']:desdata|=index[(*strB++)-'A']; return (srcdata|desdata) == srcdata ; }解法四：排序+比较
方法比较土，但是思路很好理解。大概的意思就是先将strA 和strB进行排序，然后依次从头比较strB是否在strA中，在比较的时候需要忽略掉strB中重复的数据。
解法五：素数法
解法比较新颖，但是不推荐使用。
原理：若数字num1和数字num2分别是两组素数的乘积结果，如果num1=num2，那么两组素数必定是完全相同的一组数。
证明：假设两数组中存在不同的素数。
设num1=a1*a2*a3*.....*an
num2=b1*b2*b3*.......*bm
其中，ai和bj均为素数。
∵num1=num2
∴a1*a2*a3*.....*an = b1*b2*b3*.......*bm
约去a和b中相同的素数得：..........①
a1*a2*.....*ax=b1*b2*.....*by
∴a1/b1=(b2*.....*by)/(a2*.....*ax)
易知a1/b1为最简分数形式，(b2*.....*by)和(a2*.....*ax)均为和数。故(b2*.....*by)和(a2*.....*ax)必定存在公因子，而由①可知，(b2*.....*by)和(a2*.....*ax)不存在相同的数，因此不可能存在相同的公因子，矛盾。
故两组素数必定是完全相同的一组数。