string - 最小汉明距 ionic 向量

Question

让U小字母0, 1或 A, C, G, T , k <= n .

我想找到之间的最小汉明距离 u = (u_1,...,u_k)和 v = (v_1,...,v_n) 的连续子序列长度k及时O(n log n) .

这可能吗？

感谢您的帮助!

Answer 1

对于字母表{1, -1}，多项式相乘

(u_k + u_{k-1} x + u_{k-2} x^2 + ... + u_1 x^{k-1})

和

(v_1 + v_2 x + v_3 x^2 + ... + v_n x^{n-1}).

乘积中x^i的系数是u_1 ... u_k和v_{i-k之间汉明距离的简单仿射函数+2} ... v_{i+1}.

我们可以通过嵌入其他字母表来对它们进行编码，从而计算出汉明距离，例如，

A -> 0000
C -> 0011
G -> 0101
T -> 1001.