最长公共子路径

难度: Hard

一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。

总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能重复出现，但同一个城市在一条路径中不会连续出现。

给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 0 。

一个 子路径 指的是一条路径中连续的城市序列。

示例 1：

输入：n = 5, paths = [[0,1,2,3,4],
                     [2,3,4],
                     [4,0,1,2,3]]
输出：2
解释：最长公共子路径为 [2,3] 。

示例 2：

输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有公共子路径。

示例 3：

输入：n = 5, paths = [[0,1,2,3,4],
                     [4,3,2,1,0]]
输出：1
解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。

提示：

1 <= n <= 10⁵
m == paths.length
2 <= m <= 10⁵
sum(paths[i].length) <= 10⁵
0 <= paths[i][j] < n
paths[i] 中同一个城市不会连续重复出现。

Submission

运行时间: 1443 ms

内存: 92.1 MB

def inducedSort(s: List[int], sa1: List[int], t: List[int], m: int):
    n = len(s)
    cnt = [0] * m
    for i in range(n):
        cnt[s[i]] += 1
    for i in range(1, m):
        cnt[i] += cnt[i - 1]
    start, end = [0] + cnt[:-1], cnt[:]
    sa = [-1] * n + [n]
    for x in reversed(sa1[1:]):
        cnt[s[x]] -= 1 
        sa[cnt[s[x]]] = x  
    for i in range(-1, n):
        if sa[i] > 0:
            c = sa[i] - 1 
            if not t[c]:
                sa[start[s[c]]] = c
                start[s[c]] += 1
    for i in range(n - 1, -1, -1):
        if sa[i] > 0:
            c = sa[i] - 1
            if t[c]:
                end[s[c]] -= 1
                sa[end[s[c]]] = c
    return sa[:-1]

def suffixArray(s: List[int], bucketNum: int):  
    n = len(s)
    t = [False] * (n + 1)
    for i in reversed(range(n - 1)):
        t[i] = t[i + 1] if s[i] == s[i + 1] else (s[i] < s[i + 1])
    critical = list()
    for i in range(1, n):
        if t[i] and not t[i - 1]:
            critical.append(i)
    nc = len(critical)
    index = [-1] * n + [n]
    for i, x in enumerate(critical):
        index[x] = i
    sa0 = inducedSort(s, [n] + critical, t, bucketNum) 
    s1 = [0] * (nc + 1)
    critical.append(n)
    last, p, repeat = "", 0, False
    for x in sa0:
        if index[x] >= 0:
            c = s[x : critical[index[x] + 1]]
            if c != last:
                p += 1
                last = c
            else:
                repeat = True
            s1[index[x]] = p
    if repeat:
        sa1 = [critical[x] for x in suffixArray(s1, p + 1)]
    else:
        sa1 = [n] + [x for x in sa0 if index[x] >= 0]
    return inducedSort(s, sa1, t, bucketNum)

def getHeight(s: List[int], sa: List[int]) -> List[int]:
    n, k = len(s), 0
    rk = [0] * n
    for i in range(n):
        rk[sa[i]] = i
    height = [0] * n
    s += [-1]
    for i in range(n):
        if rk[i]:
            if k > 0:
                k -= 1
            while s[i + k] == s[sa[rk[i] - 1] + k]:
                k += 1
            height[rk[i]] = k
    return height, rk

class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
        label, s = [], []
        m = len(paths)
        for i, path in enumerate(paths):
            label += [i] * (len(path) + 1)
            s += [x + m for x in path]
            s.append(m-i)

        sa = suffixArray(s, n + m)
        height, _ = getHeight(s, sa)
        height[0] = float('inf')

        cnt = [0] * m
        p, cntcnt, ans = 0, 0, 0
        q = deque()
        for i, x in enumerate(sa):
            cl = label[x]
            cnt[cl] += 1
            if cnt[cl] == 1:
                cntcnt += 1
            while q and q[-1][0] > height[i]:
                q.pop()
            q.append((height[i], i))
            while cnt[label[sa[p]]] > 1:
                if q[0][1] == p + 1:
                    q.popleft()
                cnt[label[sa[p]]] -= 1
                p += 1
            if cntcnt == m:
                c = q[0][0]
                if c > ans:
                    ans = c
        
        return ans

Explain

该题解采用后缀数组和LCP数组结合滑动窗口的方法来寻找最长公共子路径。首先，构建一个由所有路径组成的超级字符串，每个路径之间用一个特殊的分隔符隔开。然后对这个超级字符串构建后缀数组，这样就可以在O(n log n)的时间内找到所有后缀的排序。接下来，使用后缀数组计算出最长公共前缀（LCP）数组。利用LCP数组，通过滑动窗口技术来维护所有路径在当前窗口内的最小LCP值，确保窗口内包含所有路径至少一次。最后，窗口的最小LCP值即为我们要找的最长公共子路径的长度。

时间复杂度: O(n log n)

空间复杂度: O(n)

def inducedSort(s, sa1, t, m):
    # 数组s表示待排序的数字，sa1表示已排序的部分，t是类型数组，m是桶的数量
    n = len(s)
    cnt = [0] * m
    for i in range(n):
        cnt[s[i]] += 1
    for i in range(1, m):
        cnt[i] += cnt[i - 1]
    start, end = [0] + cnt[:-1], cnt[:]
    sa = [-1] * n + [n]
    for x in reversed(sa1[1:]):
        cnt[s[x]] -= 1
        sa[cnt[s[x]]] = x
    for i in range(-1, n):
        if sa[i] > 0:
            c = sa[i] - 1
            if not t[c]:
                sa[start[s[c]]] = c
                start[s[c]] += 1
    for i in range(n - 1, -1, -1):
        if sa[i] > 0:
            c = sa[i] - 1
            if t[c]:
                end[s[c]] -= 1
                sa[end[s[c]]] = c
    return sa[:-1]

def suffixArray(s, bucketNum):
    # 构建后缀数组
    n = len(s)
    t = [False] * (n + 1)
    for i in reversed(range(n - 1)):
        t[i] = t[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
    critical = [i for i in range(1, n) if t[i] and not t[i - 1]]
    index = [-1] * n + [n]
    for i, x in enumerate(critical):
        index[x] = i
    sa0 = inducedSort(s, [n] + critical, t, bucketNum)
    s1 = [0] * (nc + 1)
    critical.append(n)
    last, p, repeat = "", 0, False
    for x in sa0:
        if index[x] >= 0:
            c = s[x : critical[index[x] + 1]]
            if c != last:
                p += 1
                last = c
            else:
                repeat = True
            s1[index[x]] = p
    if repeat:
        sa1 = [critical[x] for x in suffixArray(s1, p + 1)]
    else:
        sa1 = [n] + [x for x in sa0 if index[x] >= 0]
    return inducedSort(s, sa1, t, bucketNum)

def getHeight(s, sa):
    # 计算LCP数组
    n, k = len(s), 0
    rk = [0] * n
    for i in range(n):
        rk[sa[i]] = i
    height = [0] * n
    s += [-1]
    for i in range(n):
        if rk[i]:
            if k > 0:
                k -= 1
            while s[i + k] == s[sa[rk[i] - 1] + k]:
                k += 1
            height[rk[i]] = k
    return height, rk

class Solution:
    def longestCommonSubpath(self, n, paths):
        # 寻找最长公共子路径
        label, s = [], []
        m = len(paths)
        for i, path in enumerate(paths):
            label += [i] * (len(path) + 1)
            s += [x + m for x in path]
            s.append(m-i)

        sa = suffixArray(s, n + m)
        height, _ = getHeight(s, sa)
        height[0] = float('inf')

        cnt = [0] * m
        p, cntcnt, ans = 0, 0, 0
        q = deque()
        for i, x in enumerate(sa):
            cl = label[x]
            cnt[cl] += 1
            if cnt[cl] == 1:
                cntcnt += 1
            while q and q[-1][0] > height[i]:
                q.pop()
            q.append((height[i], i))
            while cnt[label[sa[p]]] > 1:
                if q[0][1] == p + 1:
                    q.popleft()
                cnt[label[sa[p]]] -= 1
                p += 1
            if cntcnt == m:
                c = q[0][0]
                if c > ans:
                    ans = c

        return ans

Explore

在构建后缀数组的过程中，为了避免城市编号与特殊分隔符混淆，我们对城市编号进行了偏移处理，将每个城市编号加上路径的数量 m。这样，所有城市编号都会大于任何一个分隔符编号，分隔符的编号为 m-i（其中 i 是路径的索引）。通过这种方式，我们确保了城市编号与分隔符的值不会重叠，从而在后缀数组和LCP数组的计算中正确区分不同的路径。

滑动窗口在算法中用于确保每个窗口内包含所有路径至少一次。窗口初始化时，开始和结束指针都设为数组的起始位置。随着结束指针向右移动，我们增加对应后缀起始位置的路径计数，并将当前LCP值与窗口的最小值进行比较，如果有必要，更新窗口的最小值。如果发现某路径的计数超过1，开始指针向右移动，直到每个路径在窗口中至少出现一次。通过这种方式，我们可以找到同时涵盖所有路径的最小LCP区间，即为我们要找的最长公共子路径的长度。

在计算LCP数组时，在字符串末尾添加一个特殊字符（-1）是为了确保最后一个字符是全局最小的，这样可以避免在进行LCP计算时越界。因为比较时我们会检查当前后缀与前一个后缀的共同前缀，添加-1确保了在字符串尾部的比较会立即停止，因为没有其他字符会比-1更小。这样，我们能够正确地终止比较过程，避免错误地扩展LCP值。

在使用后缀数组和LCP数组寻找最长公共子路径时，我们通过在每个路径末尾添加唯一的分隔符来区分不同路径。这些分隔符在计算过程中保证了任何找到的公共子序列不会跨越多个路径。此外，通过滑动窗口技术确保每个窗口至少包含每个路径一次，我们可以保证找到的最长公共子路径是所有路径共有的，而不是由于路径内部的重复城市引起的误匹配。