让U小字母0, 1或 A, C, G, T , k <= n .
我想找到之间的最小汉明距离
u = (u_1,...,u_k)和 v = (v_1,...,v_n) 的连续子序列长度k
及时O(n log n) .
这可能吗？
感谢您的帮助!
最佳答案
对于字母表{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.
关于string - 最小汉明距 ionic 向量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33721407/