题目描述：
假设这有一个各种字母组成的字符串A，和另外一个字符串B，字符串里B的字母数相对少一些。什么方法能最快的查出所有小字符串B里的字母在大字符串A里都有？
比如，如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPO
答案是true，所有在string2里的字母string1也都有。
如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPZ
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。
#include#include #include #include #include #include using namespace std; //第一种方法：用hash_table做 //O(n+m) bool include(string &a,string &b){ hash_set 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; }