汉明距离问题

Published: by Creative Commons Licence

  • Tags:

汉明距离问题

给定两个等长的字符串,它们的汉明距离是指两个字符串对应位置不同字符的数目。

题目1:给定$n$个01字符串,每个字符串长度为$k$,要求找出汉明距离最大和最小的两对字符串。其中$1\leq n, k\leq 3\times 10^3$。

我们可以发现如果用bitset来表示两个字符串,那么$a \text{ and } b$实际上就表示各个位置是否相同,而$a \text{ xor } b$则表示各个位置是否不同。于是乎我们可以$O(\frac{n^2k}{64})$解决这个问题,常数很小。

提供一道题目

题目2:给定$n$个字符串,每个字符串长度为$k$,字符集大小为$10^4$。要求找出汉明距离最大的两对字符串。其中$1\leq n\leq 10^6$,$1\leq k\leq 6$。

这里我们可以用随机化的做法。每次随机将字符集中的字符等概率替换为$0$或$1$。可以发现在新的$n$个01字符串中找到的最大汉明距离,一定不超过我们的答案。并且实际上至少有$2^{-k}$的概率等于我们的答案。

因此从平均的角度来说,我们只需要随机大约$2^k$次,之后解决一个01字符串找最大汉明距离的问题,后者可以$O(n)$解决。总的时间复杂度为$O(2^kn)$。