1923. 最长公共子路径

解题思路：二分查找找长度，check函数判断是否符合

 def check(m):
            base = random.randint(10**6, 10**7)
            mod = (10**9 + 7) * (10**9 + 9)
            rem = pow(base,m,mod)
            res = set()          #存上一个人走过的
            for i in range(len(paths)):
                number = 0
                tmp = set()      #存这一次的 
                l = 0
                for j in range(m):
                    number = (number * base + paths[i][j])%mod
                if i == 0 or number in res:  # 上一个人走过的或者第一次出现的，如果上一个人没走过肯定不是答案，因为是公共的
                    tmp.add(number)

                for r in range(m, len(paths[i])):
                    number = (number * base + paths[i][r] - rem * paths[i][l])%mod
                    if i == 0 or number in res:
                        tmp.add(number)
                    l += 1
                if not tmp:
                    return False
                res = tmp                        #更新
            return True

        l = 1
        ans = 0
        r = min(len(i) for i in paths)
        while l <= r:
            m = l + (r - l) // 2
            if check(m):
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35