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
36
37
38
| from typing import List
from collections import defaultdict
class Solution:
def longestCommonSubpath(self, n: int, ps: List[List[int]]) -> int:
l = 0
r = min(len(path) for path in ps)
base = 100001
mod = 100000000019
while l < r:
m = (l + r + 1) // 2
hs = defaultdict(set)
for i in range(len(ps)):
hash_val = 0
d = 1
hs1 = set()
for j in range(len(ps[i])):
hash_val = (hash_val * base + ps[i][j]) % mod
if j >= m:
hash_val = (mod + hash_val - d * ps[i][j - m] % mod) % mod
else:
d = d * base % mod
if j >= m - 1 and (i == 0 or hash_val in hs):
hs1.add(hash_val)
hs = hs1 if i == 0 else hs & hs1
if not hs:
r = m - 1
else:
l = m
return l
|