汉明距离问题

Published: January 09, 2021 by Daltao

• Categories:
• algorithm 101

• 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)$。

题目3：给定字符串$S$和$T$，询问$S$有多少子串（与$T$等长）与$T$的汉明距离小于$k$。其中$1\leq |S|,|T| \leq 10^6$，$0\leq k\leq 4$。

提供一道问题。

对于一个给定的子串，我们可以通过二分+哈希很容易找到前$k$个不匹配的坐标。时间复杂度为$O(|T|+k|S|\log_2|T|)$。

题目4：给定两个字符串$a$和$b$，要求将$a$循环拼接$n$次得到$a'$，$b$循环拼接$m$次得到$b'$。保证$|a'|=|b'|$，计算$a'$与$b'$的汉明距离。其中$1\leq |a|,|b|\leq 10^6$，且$1\leq n,m\leq 10^{12}$。其字符串中的元素$e$范围满足$1\leq e\leq 10^6$。

提供一道题目。

当$|a'|> lcm(|a|,|b|)$的时候，我们可以先计算$a'$与$b'$的长度为$lcm(|a|,|b|)$的前缀的汉明距离后，乘上$|a'|/lcm(|a|,|b|)$即可得到最终结果。接下来认为$|a'|= lcm(|a|,|b|)$。

考虑$a_i$是否可能会与$b_j$处于同一位置，这等价于存在一个$k$，满足

$$\left\{ \begin{array}{} k&=&i&\pmod {\|a\|}\\ k&=&j&\pmod {\|b\|} \end{array} \right.$$

根据扩展中国余数定理知道$k$存在等价于$gcd(|a|,|b|)\mid i-j$。且$k$在模$lcm(|a|,|b|)$意义下唯一。

因此我们可以枚举$0\leq i<g$。之后判断$\left\{a_{i+kg}\right\}$与$\left\{b_{i+kg}\right\}$中有多少对元素不同，将所有结果加和就是我们的最终答案。这个过程$O(\frac{|a|+|b|}{g})$完成。

总的时间复杂度为$O(n+m+\log_2n+\log_2m)$。