设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.