字符串类面试题型之二——字符串的包含

在笔试面试中，字符串类是经常重点考的题型。本系列是本人为了准备笔试与面试，综合各类书与博客，整理所得。

希望在此过程中，希望可以深刻理解各种题型，督促自己的学习进步，并且分享给大家。如有错误，非常希望得到指点，不甚感激。

题目描述:

给定一长字符串a和一短字符串b。请问，如何最快地判断出短字符串b中的所有字符串是否都在长字符串a中？

a:  abcd

本题也是来自于《编程之法》，书中给出了4种方法。第一种还是蛮力轮询，是最直观，但是也是效率最低的方法。第二种是排序后轮询，但是此方法的效率依旧不高。第三种是素数相乘，使长字符串a中的每个字母与一个素数对应，再遍历a,把a中的每个字符串对应的素数相乘，得到一个整数。让短字符串b中的字母也对应相应的素数，再用b中的每个字母对应的素数除以上面得到的整数。如果有余数，说明结果为False，否则为Ture。它给出的第四种方法是位运算法，使用了一个散列表（hash table)，本人使用了一长度为26的数组（也可以使用HashMap）来分别表示26个字母，记录a中是否出现了相应的字母，出现则标记，并对b进行遍历，判断每个字母是否被标记过。如果都被标记过，则b为a的子串。

实现代码如下：

int StringContain(char *si, char *s2) {     int array[26] = {
   0};     int len_a = strlen(s1);     int len_b = strlen(s2);     for(i=0; i

字符串包含，也还有一种题型，就是在字符串中查找子串，并且返回子串在字符串中第一次出现的位置。

此题型也是较为简单，使用两个数组进行轮询比较即可。

实现代码如下：

int strstr(const char *str1, const char *str2) {     int i, j, len1, len2, firstplace;     if((str1 == NULL) && (str2 == NULL))     {         return ;     }     len1 = strlen(str1);     len2 = strlen(str2);     for(i=0; i<(len1-len2); i++)     {         if(str1[i] == str2[0])         {             for(j=0; j

不足之处，敬请谅解，欢迎交流。

对于题目与解法的来源，本人尽量给出出处，尊重原创，方便大家寻找。