c++ - 选择前缀数量最多的索引？

Question

我有许多 0 和 1 序列，我想找到一个具有最大数量的其他序列，这些序列构成当前序列的前缀。

例子:

std::vector<std::vector<int>> sequence={{1,1},{1},{0,1,0,1},{1,1,0}}

{1,1} 只有 1 个前缀，即 {1}。

但是 {1,1,0} 有 2 个前缀 {1,1} 和 {1}。因为它有最多的前缀计数，我想选择 sequence 的索引 3。 我可以用嵌套循环来做，但是它消耗了很多时间，因为我必须处理大小为 的序列512.感谢您的帮助。

到目前为止我做了什么:

bool isPrefixOf(std::vector<int> current, std::vector<int> other){
  if (other.size()>current.size())
      return false;
  for (int i=0; i<other.size(); ++i) {
      if (other[i] != current[i]) 
          return false;
    }
  return true; 
}

int len = sequence.size();
int max = 0;
int selected = -1;
int prefix_count;
for(int i=0; i<len; i++){
    prefix_count = 0;
    for(int j=0; j<len; j++){
      if(isPrefixOf(sequence[i],sequence[j])) ++prefix_count;
    }
    if(prefix_count >= max){
      max = prefix_count;
      selected = i;
    }
  }

Answer 1

您的双循环导致 O(n²) 算法。如果你构建一个 prefix tree，你可以获得一个 O(n) (在你的情况下是二进制文件)如下:

• 对于每个单个序列，迭代值，在 0 上跟随左 child ，在 1 上跟随右 child 。如果不存在，则创建新的 child 。
• 如果序列完成，递增当前节点(无论是否为叶子!)。变体:如果你不想计算重复项，只需将节点值设置为 1(无论之前是否)。
• 只对叶子感兴趣，因为任何父节点都与叶子共享前缀，但它本身就是一个前缀，因此叶子将(至少)多一个前缀。
• 对于每个叶子，求和从根到叶子的路径上的值。
• 具有最大值的叶子标记了您之后的序列；计算和的时候可以记住最大的权利，这样就不用走两次树了

对于您给出的示例，树将如下所示:

      [0] (root, always 0)
     /   \
    /(0)  \(1)
   /       \
 [0]       [1] (one sequence finished here!)
   \         \
    \(1)      \(1)
     \         \
     [0]       [1]
     /          /
    /(0)       /(0)
   /          / 
 [0]        [1]<3>
   \
    \(1)
     \
     [1]<1>

在总和中包括叶子将正确地考虑叶子中的重复项。这将包括形成到叶子本身的路径的序列(解释:每个序列都是其自身的前缀)，但是对于 every 叶子就是这种情况，你得到的偏移量都是 1 ，所以这对最大值没有影响，你在...

您还可以将通向该节点的序列的索引存储在节点内，以便在原始 vector 中进行更快的访问。