第二章：字符串是否包含问题-白红宇

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

阅读量：4136 次

发布时间：2019-05-25

本文共 1451 字，大约阅读时间需要 4 分钟。

题目描述：

假设这有一个各种字母组成的字符串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;}

转载地址：http://gfvvi.baihongyu.com/

你可能感兴趣的文章