树中根起始路径匹配模式P的子路径线性时间算法求解

这个问题不需要使用动态规划，借助KMP字符串匹配算法结合树的深度优先遍历即可实现线性时间复杂度的求解，完全满足题目要求。

算法思路 #

题目要求匹配的子路径全部位于根节点出发的有向路径上，本质等价于：在树的所有根到叶路径拼接成的文本集合中，找出所有和模式串P完全匹配的子串。如果单独对每条根到叶路径独立跑KMP，公共前缀部分会被重复计算，无法达到线性时间。我们可以在遍历树的过程中复用KMP的匹配状态，利用树的公共前缀特性消除重复计算。

详细执行步骤 #

• 模式串预处理：设模式串P长度为m，预先计算KMP算法的失败函数（即next数组），记录每个位置匹配失败时最长可回退的公共前后缀长度，这一步的时间复杂度为O(m)。
• 带匹配状态的深度优先遍历：
  • 维护一个全局匹配状态变量j，表示当前遍历位置已经匹配到P的前j个字符，根节点初始状态为j=0。
  • 从根节点出发递归遍历所有子节点：
    • 每遍历一条从父节点指向子节点的边时，按边的标注顺序逐个处理边上的每个字符：
      • 按照标准KMP规则更新状态j：若j == m，先将j回退到next[j-1]以支持重叠场景的匹配；若当前字符和P[j]相等则j += 1，否则不断通过next数组回退j，直到j=0或者找到匹配的前缀位置后再累加j。
      • 每次更新完j立刻做判断：若j == m，说明当前位置刚好完成一次完整匹配，记录该匹配的信息：终点为当前边的当前字符位置，起点为根路径上往前数m个字符对应的位置，这就是一个符合题目要求的子路径。
    • 处理完整条边到达子节点时，先保存当前的j值作为该子节点的入口匹配状态，再递归遍历该子节点的所有后代节点。
    • 子节点的所有后代遍历完成后，直接将j恢复为进入该子节点之前保存的父节点状态，完成回溯，不需要重新计算路径上的匹配状态。

时间复杂度证明 #

• 模式串预处理的开销为O(|P|)，和模式串长度线性相关。
• 遍历树的过程中，每条边上的每个字符只会被处理一次：处理字符时j的总增量等于树所有边的总字符数，而j的回退操作总次数永远不会超过j的总增量，因此字符处理的总开销和树的总字符数线性相关。
• 节点状态保存、回溯恢复的操作单次开销为O(1)，总次数等于树的节点总数；由于每条边至少包含1个字符，树的节点数不会超过总字符数+1，这部分开销同样是线性的。

整体时间复杂度恰好为O(|P| + 树所有边的总字符数)，完全满足题目要求的线性时间约束。

内容的提问来源于stack exchange，提问作者John Baker