Phi*_*ppe 6 algorithm dynamic-programming
我需要一个表示一组序列(所有相同,已知,长度)的数据结构,具有以下非标准操作:
在集合中找到两个恰好在一个索引上不同的序列.(或确定不存在这样的对.)
如果N是序列的长度和序列M的数量,则有一个明显的O(N*M*M)算法.我想知道是否有一种更有效地解决这个问题的标准方法.如果需要,我愿意应用预处理.
奖励点如果不是返回一对,则算法返回在同一点上不同的所有序列.
或者,我也对一个解决方案感兴趣,我可以有效地检查特定序列在一个索引处是否与该集合中的任何序列不同.如果它有帮助,我们可以假设在集合中,没有两个序列具有该属性.
编辑:你可以假设N相当小.通过这个,我的意思是改进,例如O(log(N)*M*M)对我的用例不是立即有用.
对于每个序列和该序列中的每个位置 i，计算不包含位置 i 的序列的哈希值并将其添加到哈希表中。如果表中已有条目，则您已找到仅在一个位置不同的潜在对。使用从开始和结束的滚动哈希并将它们组合起来，您可以在恒定时间内计算每个哈希。预计总运行时间为 O(N*M)。