1.2 字符串包含

题目：给定长字符串a和段字符串b，如何判断短字符串中所有字符均在长字符串a中？
示例：
a="ABCD", b="BAD" 返回true；
a="ABCD", b="BCE" 返回false；
a="ABCD", b="AAA" 返回true；
解法1：排序后轮询，拿着字符串b中的每一个字符去字符串a中查询

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool stringcontain(string &a,string &b)
{
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for(int pa =0,pb=0;pb<b.length();) //每次从b中取出一个字符，在a中进行查询
    {
        //如果还没查到字符串a的尾部，或者a中目前查到的元素比b中被查询的元素还小，则把pa后移一位
        while((pa<a.length())&&(a[pa]<b[pb]))
        {
            ++pa;
        }
        //如果pa都到头了，还没有找到目标元素，或者a中的元素都比目标元素大了（之前排过序，比如要查字典中B开头单词，结果都翻到C开头的部分了还没找到想找的单词），则说明字符串a中不存在目标元素
        if((pa>=a.length())||(a[pa]>b[pb]))
        {return false;}
        ++pb;
    }
    return true;
}
int main(int argc, char *argv[])
{
    string s1="ABCDE";
    string s2="AAAA";
    if(stringcontain(s1,s2))
        cout <<"true"<<endl;
    else
        cout << "false"<<endl;
    return 0;
}

解法2：位运算

#include <iostream>
#include <string>
using namespace std;

bool stringcontain(string &a,string &b)
{
    int hash=0;
    for(int i=0;i<a.length();++i)
    {
        hash|=(1<<(a[i]-'A'));
    }
    for(int i=0;i<b.length();++i)
    {
    //依次用字符串b中每一个字符去与前面得到的hash相与，如果相与得0说明有不同字符（与运算的规则是“一一得1，其余得0”），因此如果有不存在的字符就得0
        if((hash &(1 <<(b[i]-'A')))==0)
        {
            return false;
        }
    }
    return true;
}
int main(int argc, char *argv[])
{
    string s1="ABCDE";
    string s2="AASAA";
    if(stringcontain(s1,s2))
        cout <<"true"<<endl;
    else
        cout << "false"<<endl;
    cout << (1<<0x00);
    return 0;
}