第二章：字符串是否包含问题

题目描述：
假设这有一个各种字母组成的字符串A，和另外一个字符串B，字符串里B的字母数相对少一些。什么方法能最快的查出所有小字符串B里的字母在大字符串A里都有？

比如，如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPO
答案是true，所有在string2里的字母string1也都有。
  
如果是下面两个字符串：  
String 1: ABCDEFGHLMNOPQRS   
String 2: DCGSRQPZ  
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <hash_set>
using namespace std;

//第一种方法：用hash_table做
//O(n+m)
bool include(string &a,string &b){
	hash_set<char> hs;
	for(char t:a)
		hs.insert(t);
	for(char t:b)
		if(hs.find(t)==hs.end())return false;
	return true;
}
//第二种方法：素数方法，学习了
//O(m+n)
// 素数数组  
int primeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,  
                        61, 67, 71, 73, 79, 83, 89, 97, 101}; 
bool include2(string &a,string &b){
	 // 这里需要用到大整数  
    long long product = 1;   //大整数除法的代码，下头给出。  
  
    // 遍历长字符串，得到每个字符对应素数的乘积  
    for (char t:a){  
        int index = t - ‘A‘;  
        product = product * primeNumber[index];  
    }
  
    // 遍历短字符串  
    for (char t:b){  
        int index = t - ‘A‘;  
  
        // 如果余数不为0，说明不包括短字串中的字符，跳出循环  
        if (product % primeNumber[index] != 0)  
            return false;  
    }  
	return true;
}
//第三种方法，用二进制的位来表示是否存在
bool include3(char *a,char *b){
	int have = 0;    
    while (*a) {    
        have |= 1 << (*(a++) - ‘A‘);   // 把A..Z对应为0..26    
    }    
    while (*b) {    
        if ((have & (1 << (*(b++) - ‘A‘))) == 0) {    
            return false;    
        }    
    }    
    return true;
}
int main(){
	//freopen("C:\\in.txt","r",stdin);
	string a= "ABCDEFGHLMNOPQRS";
	string b = "DCGSRQPO";
	if(include(a,b))cout<<"包含\n";
	if(include(a,b))cout<<"包含\n";
	return 0;
}

第二章：字符串是否包含问题

原文：http://blog.csdn.net/starcuan/article/details/19016367