视 《一次谷歌面试趣事》 后感

看 《一次谷歌面试趣事》 后感

刚看了一篇文章 《一次谷歌面试趣事》，大概说的是 面试中 遇到一个问题： 

两个字符串 ：s1 : aabbddeffgsdfs   s2: fdscxsad ，怎么快速的 算出 s2 的字符 都在 s1 里出现过。

原文网址：点击打开链接

文中 说了 4种 方法：

1.暴力搜索法 2.排序查找法 3.哈希表法（这个 不太懂） 4. 利用 素数 来算的 方法

其中 最 奇思妙想的 就是 第四种 ，

心中惊叹万分，于是 编写了 下面的 代码。

// find.cpp : 定义控制台应用程序的入口点。
//查找 

#include "stdafx.h"
#include <cstring>
#include <climits>
//a~z对应的素数
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,
};

//p里所有的字母 是否都能在 s里查到，能 返回 true,否则，false
//字母限定 在 a~z
bool isAllMatch(char * string,char * subString){
	char * p = string;
    <span style="white-space:pre">	</span>long long int mult = 1;
	while (*p != '\0')
	{
		int index = *p - 'a';
		int temp =  primeNumber[index];
		mult *= temp;
		p++;
	}
	p = subString;
	while (*p != '\0')
	{
		int index = *p - 'a';
		if (mult % primeNumber[index] != 0)
		{
			return false;
		}
		p++;
	}
	return true;
}


int _tmain(int argc, _TCHAR* argv[])
{
	char string[100];
	char subString[100];
	while (1)
	{
		printf("请输入两个字符串（范围限制：a~z),输出 exit 结束:\n");
		scanf("%s%s",string,subString);
		if (strcmp(string,"exit") == 0)
		{
			break;
		}
		char * isMatch = isAllMatch(string,subString) ? "是" : "不是";
		printf("%s 的 字符 都能 在 %s里查找到?:%s\n",subString,string,isMatch);
	}
	return 0;
}

可是 运行中 遇到了一些 问题：当 输入 15个z ，查找串也是 15个z的时候，却 显示 ： “不是”

问题 出在 这一段：

 long long int mult = 1;
	while (*p != '\0')
	{
		int index = *p - 'a';
		int temp =  primeNumber[index];
		mult *= temp;
		p++;
	}

mult 溢出了。。。可是 multb 已经 是 Long long int 了， 看来 第四个算法 是 个 垃圾 算法。

任何 好的 算法 如果 不能被 计算机所识别，都不是一个 好的 算法。