C语言练习第四天 字符串是否包含问题 补充

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

比如，如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPO
答案是true，所有在string2里的字母string1也都有。

如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPZ
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

问题及主要思路来自于 July
链接: link.

第三种方法 散列表法

这种方法其实就是用一个矩阵 每个元素代表一个字母
先将所有元素置为 0 ；
扫描str2 -----> 每扫描到一个字母 将对应的矩阵元素置为 1
如下表示例所示 eg. str2[] = “ABCDE”; str1[] = “ABCDEF”;

设矩阵为a[26] = {0}； <| -------|> 用这个公式来计算每个元素对应该数组的地址 str2[2] - ‘A’ = 1
所以第二个元素对应的数组元素为 a[1]
每扫描到一个字母 num++
列表如下

字母	对应元素	数值
A	a[0]	1
B	a[1]	1
C	a[2]	1
D	a[3]	1
E	a[4]	1
F	a[5]	0

这样 再扫描str1 每扫描到一个字母 如果该字母在a[]的对应位置值为1 则将该位置的值置为 0 ,并且num–；直到num = 0,呢么说明str2中所有元素在str1中都已经找到 打印ture 并返回1
如果直到循环结束 num的值还不为0 呢么至少str2中至少有大于等于一个元素str1中没有
呢么说明 str1 不能包含 str2 打印false 并返回0；

这个算法比较容易理解 且复杂度只有o(m+n) 较为推荐 但是其对电脑的内存占用率要高 即空间复杂度较高.

代码如下

//散列表比较法
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void hashtable(char* s1, char* s2){
	int hash[26] = { 0 };
	int i = 0;
	int num = 0;
	int hashb = 0;
	for (i = 0; i < strlen(s2); i++){
		hashb = s2[i] - 'A';
		if (hash[hashb] == 0){
			hash[hashb] = 1;
			num++;
		}
	}
	for (i = 0; i < strlen(s1); i++){
		hashb = s1[i] - 'A';
		if (hash[hashb] == 1){
			hash[hashb] = 0;
			num--;
		}
		if (num == 0) break;
	}
	if (num == 0) puts("true");
	else puts("false");

	return;
}
//测试函数
int main(void){
	char str1[] = "ABCDEFGHLMNOPQRS";
	char str2[] = "DCGSRQPO";
	
	//hashtable(散列表)比较法
	hashtable(str1, str2);
	return 0;
}

第四种方法 素数法

这个方法就是将A~Z每个字母对应一个素数 因为素数的约数只有1和它本身
扫描 str1 将每个元素对应素数的乘积储存在一个长整形中(因为最后数字会很大，本例选用unsigned long int 类型)，然后扫描str2 用上述的乘积值(本例设为product）去除以str2中元素对应的素数值
若能被整除 呢么说明这个元素 str1中有 若不能 则这个元素在str1中没有
若遇见一个不能被整除的元素 呢么打印flase
若所有元素均能够被整除 呢么打印true

这个算法的复杂度是动态的 因为不用扫描str2中的所有元素
所以复杂度为o(n) ~ o(m+n)
代码如下

//素数法
//这个函数用来判断素数
//算法缺点 字符串过长时 需要定义超长类型的整形来储存数据
//而且往往数据储存较为困难 不适合用于长字符串过长的情况
//比如 测试用字符串
	/*char str1[] = "DCGSRQPOABCDEFGHI";
	  char str2[] = "DCGSRQPO";*/
//这样运行会显示false，但实际程序正确运行会显示ture
//原因可能是unsigned long int的数据类型无法承载product的大小
//如果 测试用字符串为
	/*char str1[] = "DCGSRQPOABCDEFGH";
	  char str2[] = "DCGSRQPO";*/
//这样程序就会正确运行
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int my_prine_num(int x){
	int i = 0;
	if(x == 2) return x;
	for(i = 2;i <= x/2;i++){
		if(x%i == 0){
			return 0;
		}
	}
	return x;
}
int prime_num_cp(char* s1,char* s2){
	//找到24个素数并赋值给A ~ Z 因为这个步骤可以提前赋值好
	//所以不算在复杂度里面
	int i = 0;
	int n = 0;
	int num_letter[26] = {0};
	//给26个字母分别赋值 并将值储存在num_letter中
	for(i = 2;n < 26;i++){
		if(my_prine_num(i) != 0){
			num_letter[n] = my_prine_num(i);
			n++;
		}
	}

	//从这里开始计算复杂度
	//历遍长字符串 并计算素数的乘积
	int index = 0;
	unsigned long int product = 1;
	for(i = 0;i < strlen(s1);i++){
		index = s1[i] - 'A';
		product = num_letter[index] * product;
	}

	//历遍短字符串，看看是否能被整除
	for(i = 0;i < strlen(s2);i++){
		index = s2[i] - 'A';
		if(product%num_letter[index] != 0){
			puts("false");
			return 0;
		}
	}
	
	//表示历遍了所有短字符串的元素且对应素数都能被
	//product整除
	puts("ture");
	return 1;

	//所以总的复杂度为o(n) ~ o(m+n)
}


//测试函数
int main(void){
	char str1[] = "ABCDEFGHLMNOPQRS";
	char str2[] = "DCGSRQPO";

	//素数法
	prime_num_cp(str1,str2);
	return 0;
}

这个算法的不足之处在于如果str1过长 需要储存的素数乘积就很大 需要能储存很大数字的数据类型
比如在本例中

测试用字符串
char str1[] = “DCGSRQPOABCDEFGHI”;
char str2[] = “DCGSRQPO”;
这样运行会显示false，但实际程序正确运行会显示ture
原因可能是unsigned long int的数据类型无法承载product的大小
如果 测试用字符串为
char str1[] = “DCGSRQPOABCDEFGH”;
char str2[] = “DCGSRQPO”;
这样程序就会正确运行

所以这个算法不适用于字符换过长时用来比较字符换

字符串是否包含问题 博主就能理解和处理这几种方法 如果有更好的算法或者代码有错误的地方 欢迎大家评论指证 我是 卧槽你有120斤 我们下个问题再见

本文章仅用于C语言连续和分享优秀算法