给定长度为N的查询字符串Q,以及长度恰好为N的M个序列的列表L,找到L中具有最少错配位置的字符串的最有效算法是什么？例如:
Q = "ABCDEFG";
L = ["ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT"];
answer = L.query(Q); # Returns "ABCCEFG"
answer2 = L.query("AAAATAA"); #Returns "AAAAAAA".
显而易见的方法是扫描L中的每个序列,使搜索采用O(M*N).在次线性时间有没有办法做到这一点？我不在乎将L组织到某个数据结构中需要大量的前期成本,因为它会被查询很多次.此外,任意处理捆绑分数也没问题.
编辑:为了澄清,我正在寻找汉明距离.