Select 哪个索引的前缀数最多？

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}。因为它有最多的前缀计数，我想 select sequence. 的索引 3 我可以用嵌套循环来做，但是它消耗了很多时间，因为我必须处理大小为 [=24 的序列=]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。如果不存在，则创建新的 children。
如果序列完成，递增当前节点（无论是否为叶子！）。变体：如果你不想重复计数，只需将节点值设置为1（无论之前是否）。
只对叶子感兴趣，因为任何 parent 节点都与叶子共享前缀，但它本身就是一个前缀，因此叶子将（至少）多一个前缀。
对于每个叶子，求和从根到叶子的路径上的值。
最大的叶子标记了您之后的序列；求和的时候可以记住最大的权利，这样就不用再走两次树了

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

      [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对于所有人都是平等的，所以这对最大值没有影响，你正在追求...

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

Select 哪个索引的前缀数最多？

Select the index which has the most number of prefixes among others?

c++

algorithm

prefix

stdvector