Longest Common Subpath LeetCode solution in Python

1
class Solution:
2
    def longestCommonSubpath(self, n, paths) -> int:
3
        def get_common_subpath_hashes(k):
4
            """Return hash values of common subpaths of length k, or empty set if none exists"""
5

6
            def get_subpath_hashes(path):
7
                hash, coeff = 0, pow(n, k - 1, mod)
8
                for i in range(len(path) + 1):
9
                    if i < k:
10
                        hash = (hash * n + path[i]) % mod
11
                    else:
12
                        yield hash
13
                        if i < len(path):
14
                            hash = ((hash - coeff * path[i - k]) * n + path[i]) % mod
15

16
            return reduce(set.intersection, (set(get_subpath_hashes(p)) for p in paths))
17

18
        # can be replaced with a pre-computed large prime
19
        mod = self._generate_large_prime(int(1e18), int(9e18))
20
        low, high = 1, min(len(p) for p in paths) + 1
21
        while low < high:
22
            mid = (low + high) // 2
23
            if get_common_subpath_hashes(mid):
24
                low = mid + 1
25
            else:
26
                high = mid
27
        return high - 1
28

29
    def _generate_large_prime(self, lower, upper):
30
        """Generate a prime between [lower, upper)"""
31

32
        def is_prime(n, trials=50):
33
            def witness(a, n):
34
                x0 = pow(a, u, n)
35
                for _ in range(t):
36
                    x = x0**2 % n
37
                    if x == 1 and x0 != 1 and x0 != n - 1:
38
                        return True
39
                    x0 = x
40
                return True if x0 != 1 else False
41

42
            t, u = 0, n - 1
43
            while u % 2 == 0:
44
                t, u = t + 1, u >> 1
45
            return not any(witness(randrange(1, n), n) for _ in range(trials))
46

47
        return next(
48
            r for r in iter(lambda: randrange(lower, upper), None) if is_prime(r)
49
        )