终于发现了素数的一种用途

以前只知道素数的定义:质数又称素数。一个大于 1 的自然数,除了 1 和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。今天在学习《编程之法》(github) 时,第一章第二节 “字符串包含”,其提到的一种算法用到了素数,在此仅摘取原文部分内容作为记录。需要注意的是,这种算法并不是这个问题的最优解,具体请查看原文。

以下为原文摘录:


字符串包含

题目描述:
给定两个分别由字母组成的字符串 A 和字符串 B,字符串 B 的长度比字符串 A 短。请问,如何最快地判断字符串 B 中所有字母是否都在字符串 A 里?

为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数 bool StringContains(string &A, string &B)

比如,如果是下面两个字符串:

String 1:ABCD

String 2:BAD

答案是 true,即 String2 里的字母在 String1 里也都有,或者说 String2 是 String1 的真子集。

如果是下面两个字符串:

String 1:ABCD

String 2:BCE

答案是 false,因为字符串 String2 里的 E 字母不在字符串 String1 里。

同时,如果 string1:ABCD,string 2:AA,同样返回 true。

……此处省略部分内容……

解法三

有没有比快速排序更好的方法呢?

我们换一种角度思考本问题:

假设有一个仅由字母组成字串,让每个字母与一个素数对应,从 2 开始,往后类推,A 对应 2,B 对应 3,C 对应 5,……。遍历第一个字串,把每个字母对应素数相乘。最终会得到一个整数。

利用上面字母和素数的对应关系,对应第二个字符串中的字母,然后轮询,用每个字母对应的素数除前面得到的整数。如果结果有余数,说明结果为 false。如果整个过程中没有余数,则说明第二个字符串是第一个的子集了(判断是不是真子集,可以比较两个字符串对应的素数乘积,若相等则不是真子集)。

思路总结如下:

  1. 按照从小到大的顺序,用26个素数分别与字符’A’到’Z’一一对应。
  2. 遍历长字符串,求得每个字符对应素数的乘积。
  3. 遍历短字符串,判断乘积能否被短字符串中的字符对应的素数整除。
  4. 输出结果。

如前所述,算法的时间复杂度为 O(m+n) 的最好的情况为 O(n)(遍历短的字符串的第一个数,与长字符串素数的乘积相除,即出现余数,便可退出程序,返回 false),n 为长字串的长度,空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//此方法只有理论意义,因为整数乘积很大,有溢出风险
bool StringContain(string &a,string &b)
{
const int p[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};
int f = 1;
for (int i = 0; i < a.length(); ++i)
{
int x = p[a[i] - 'A'];
if (f % x)
{
f *= x;
}
}
for (int i = 0; i < b.length(); ++i)
{
int x = p[b[i] - 'A'];
if (f % x)
{
return false;
}
}
return true;
}

此种素数相乘的方法看似完美,但缺点是素数相乘的结果容易导致整数溢出。

……此处省略部分内容……