c++ - 如何聚合序列中的循环？

Question

我有一个成对的 vector ，表示节点之间的跳数，当有循环时我想折叠它(如在一个循环中的跳数之间的总时间以将其显示为一个)。因此，例如，路径 A --> B --> C --> D --> B --> C --> D --> E 遍历子路径 B--> C --> D 两次，所以在我的结构中我会有类似的东西:

(A,B,1)(B,C,3)(C,D,2)(D,B,4)(B,C,5)(C,D,8)(D,E,6)

理想情况下我会减少到:

(A,B,1)(B,C,3+5)(C,D,2+8)(D,E,6)

还存储从 D 到 B 的 4(环回边缘时间)以单独聚合并能够以压缩方式显示 B --> C --> D(聚合边缘时间和聚合环回)所有 D-->B 实例的时间以及我们循环次数的计数)

我该怎么做？

Answer 1

我会选择后缀数组 或后缀树。只需生成标记(在本例中为 (from, to) )并将其放入后缀数组或后缀树中。然后你可以得到对。简单但不高效的方法:

产生 token ，产生这个 token 流的所有后缀。对它们进行排序。然后您在该排序列表中的所有公共(public)子序列彼此靠近(标记流长度 - 标记流后缀长度 = 位置)例如，您可以使用快速排序进行排序，或者您只是在寻找后缀数组实现。后缀数组可以在 O(n) 和 O(n) 空间内构造。并且可以在 O(n+k) 中找到最大对/重复(这就是你想要的)(其中 n = 标记数，k = 列表中的循环)

也许 this帮助。然后你可以生成一个 token 流，如:ABCDBCDE

快速而肮脏的解决方案是 here