k条路径的最长公共路径怎么求？Amazon面试算法题求解

这是一道亚马逊现场面试题，题目要求给定多名小学生从学校到家的有序行走路径，找出覆盖所有路径的最长公共子路径。

示例说明 #

示例1 #

输入路径：

child1 : a -> g -> c -> b -> e
child2 : f -> g -> c -> b -> u
child3 : h -> g -> c -> b -> x

输出结果：g -> c -> b

输入格式 #

孩子数量不固定，原始输入为(childID, 步骤节点)格式的流式数据，输入样例如下：

(child1, a)
(child2, f)
(child1, g)
(child3, h)
(child1, c)
...

常见错误思路 #

很多人第一反应是用两两计算最长公共子串的思路求解，但该方案存在明显缺陷，反例如下：

路径1：a-b-c-d-e-f-g
路径2：a-b-c-x-y-f-g
路径3：m-n-o-p-f-g
路径4：m-x-o-p-f-g

两两计算最长公共子串会得到路径1、2的公共子串abc，路径3、4的公共子串pfg，进而错误判定不存在所有路径共有的子路径，但实际正确答案是fg。

正确求解方案 #

该问题本质是求k个序列的最长公共连续子串，最优方案是滚动哈希（Rabin-Karp）+ 二分答案，实现逻辑如下：

• 预处理输入：按childID对输入做分组，还原每个孩子的行走路径，得到k条按顺序排列的节点序列，同时记录最短路径的长度作为后续二分的上界。
• 二分枚举公共子路径长度：枚举范围为0到最短路径长度，每次取中间值L判断是否存在长度为L的公共子路径。
• 校验长度L是否可行：计算所有路径中所有长度为L的连续子串的哈希值，统计是否有哈希值在全部k条路径中都出现。如果存在说明L可行，尝试更大的长度；否则尝试更小的长度。
• 提取结果：二分找到最大可行长度后，取出对应的子路径即为最终答案。

如果担心哈希碰撞问题，可以采用双哈希策略（用两组不同的基数和模数计算哈希，两组哈希同时匹配才判定为子串相同），几乎可以完全避免碰撞问题。

内容的提问来源于stack exchange，提问作者Pankaj Sharma