旋转字符串以找到等于K的汉明距离

Question

我们得到了两个长度为N和整数K的二进制字符串(A和B(。我们需要检查字符串B是否存在旋转，其中a和旋转后的字符串之间的hamming距离等于K。我们可以在一次操作中从前面删除一个字符并将其放在后面。

例如：假设我们得到这2个字符串，其值为A＝"A"；01011"；并且B＝"；01110"；并且K＝4。

注：二进制字符串之间的汉明距离是指字符串中两个对应比特不同的比特位置的数量。

在上面的例子中，答案将是"；"是"；就好像我们旋转弦B；11100"；，其hamming距离为4，等于K.

方法：

For every rotated string of B 
check that hamming distance with A
if hamming distance == K:
return "YES"
return "NO"

但显然，上述方法将在O(字符串长度x字符串长度(次中执行。有没有更好的方法来解决这个问题。由于我们不需要找到实际的字符串，我只是想知道有什么更好的算法可以得到这个答案。

限制：

Length of each string <= 2000
Number of test cases to run in one file <=600

Answer 1

首先注意，我们可以将汉明距离计算为所有i的a[i]*(1-b[i]) + b[i]*(1-a[i])的和。这简化为CCD_ 3。现在在O(n)中，我们可以计算所有i的a[i]和b[i]的和，这不会随着比特旋转而改变，所以唯一有趣的项是2*a[i]*b[i]。通过注意它等价于a和b的循环卷积，我们可以有效地计算所有比特旋转的这个项。我们可以在O(n-logn(时间内使用离散傅立叶变换来有效地计算这种卷积。

例如，在Python中使用numpy:

import numpy as np
def hdist(a, b):
return sum(bool(ai) ^ bool(bi) for ai, bi in zip(a, b))
def slow_circular_hdist(a, b):
return [hdist(a, b[i:] + b[:i]) for i in range(len(b))]
def circular_convolution(a, b):
return np.real(np.fft.ifft(np.fft.fft(a)*np.fft.fft(b[::-1])))[::-1]
def fast_circular_hdist(a, b):
hdist = np.sum(a) + np.sum(b) - 2*circular_convolution(a, b)
return list(np.rint(hdist).astype(int))

用法：

>>> a = [0, 1, 0, 1, 1]
>>> b = [0, 1, 1, 1, 0]
>>> slow_circular_hdist(a, b)
[2, 4, 2, 2, 2]
>>> fast_circular_hdist(a, b)
[2, 4, 2, 2, 2]

速度和大正确性测试：

>>> x = list((np.random.random(5000) < 0.5).astype(int))
>>> y = list((np.random.random(5000) < 0.5).astype(int))
>>> s = time.time(); slow_circular_hdist(x, y); print(time.time() - s)
6.682933807373047
>>> s = time.time(); fast_circular_hdist(x, y); print(time.time() - s)
0.008500814437866211
>>> slow_circular_hdist(x, y) == fast_circular_hdist(x, y)
True