6

我需要一个数据结构来表示具有以下非标准操作的一组序列（全部相同，已知长度）：

在集合中找到两个恰好在一个索引处不同的序列。（或确定不存在这样的对。）

如果N是序列的长度和序列M的数量，则有一个明显的O(N*M*M)算法。我想知道是否有更有效地解决这个问题的标准方法。如果需要，我愿意应用预处理。

如果算法不返回一对，而是返回在同一点不同的所有序列，则加分。

或者，我也对一种解决方案感兴趣，在该解决方案中，我可以有效地检查特定序列在一个索引处是否与集合中的任何序列不同。如果有帮助，我们可以假设在集合中，没有两个序列具有该属性。

编辑：您可以假设N相当小。我的意思是改进，例如O(log(N)*M*M)对我的用例没有立即有用的改进。

4

3 回答 3

2

对于每个序列和该序列中的每个位置 i，计算没有位置 i 的序列的哈希并将其添加到哈希表中。如果表中已经有一个条目，则您找到了仅在一个位置不同的潜在货币对。使用从开始到结束的滚动哈希并将它们组合起来，您可以在恒定时间内计算每个哈希。总运行时间预计为 O(N*M)。

于 2013-05-03T12:02:17.883 回答
0

随机选择 j 组 k 个索引（确保没有一组重叠）。

对于每个集合 XOR 元素。

现在每个文档都有 j 个指纹。

根据这些指纹比较序列。如果序列确实匹配，j-1 指纹应该匹配。但反之亦然，您可能必须逐个检查位置。

比较部分的更多说明：对所有文档中的所有指纹进行排序（或使用哈希表）。这样，您不必比较每一对，而只需比较确实具有匹配指纹的对。

于 2013-05-02T15:37:21.960 回答
0

一个简单的递归方法：

  • 通过排序或散列查找具有相同前半部分的所有序列集。

  • 对于这些集合中的每一个，重复整个过程，现在只看下半部分。

  • 通过排序或散列查找具有相同后半部分的所有序列集。

  • 对于这些集合中的每一个，重复整个过程，现在只看前半部分。

  • 当你达到长度 1 时，所有不匹配的都是你要找的。

伪代码：

findPairs(1, N)

findPairs(set, start, end)
  mid = (start + end)/2
  sort set according to start and mid indices
  if end - start == 1
    last = ''
    for each seq: set
      if last != '' and seq != last
        DONE - PAIR FOUND
      last = seq
  else
    newSet = {}
    last = ''
    for each seq: set
      if newSet.length > 1 and seq and last don't match from start to mid indices
        findPairs(newSet, mid, end)
        newSet = {}
      newSet += seq
      last = seq

修改代码以找到所有对应该很容易。

复杂？我可能错了，但是：

最大深度为log M。（我相信）最坏的情况是所有序列都相同。在这种情况下所做的工作O(N*M*log M*log M)将比O(N*M*M).

于 2013-05-02T20:24:37.950 回答