<p>There is a country of <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code>. In this country, there is a road connecting <b>every pair</b> of cities.</p>

<p>There are <code>m</code> friends numbered from <code>0</code> to <code>m - 1</code> who are traveling through the country. Each one of them will take a path consisting of some cities. Each path is represented by an integer array that contains the visited cities in order. The path may contain a city <strong>more than once</strong>, but the same city will not be listed consecutively.</p>

<p>Given an integer <code>n</code> and a 2D integer array <code>paths</code> where <code>paths[i]</code> is an integer array representing the path of the <code>i<sup>th</sup></code> friend, return <em>the length of the <strong>longest common subpath</strong> that is shared by <strong>every</strong> friend&#39;s path, or </em><code>0</code><em> if there is no common subpath at all</em>.</p>

<p>A <strong>subpath</strong> of a path is a contiguous sequence of cities within that path.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5, paths = [[0,1,<u>2,3</u>,4],
                       [<u>2,3</u>,4],
                       [4,0,1,<u>2,3</u>]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest common subpath is [2,3].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, paths = [[0],[1],[2]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no common subpath shared by the three paths.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 5, paths = [[<u>0</u>,1,2,3,4],
                       [4,3,2,1,<u>0</u>]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The possible longest common subpaths are [0], [1], [2], [3], and [4]. All have a length of 1.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>m == paths.length</code></li>
	<li><code>2 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>sum(paths[i].length) &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= paths[i][j] &lt; n</code></li>
	<li>The same city is not listed multiple times consecutively in <code>paths[i]</code>.</li>
</ul>

class Solution:
    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
        # there's a road among every pair of cities 0..n-1

        # m friends 0..m-1

        # each takes a path of 1+ cities, in order paths[i]

        # paths may have duplicates, but not adjacent duplicates

        # given n (num cities) and the paths, return the length of the longest common subpath shared by every friend's path

        # n is 1e5
        # m is 1e5
        # total length of paths is 1e5

        # tough problem, not obvious

        # although... since the longest common subpath must obviously be a subpath of at least one of the friends (duh)
        # we can start with the shortest path in paths as the longest possible subpath
        # the longest actual will be the longest subpath of that shortest path that is also a subpath of all other friends (ugh)

        # let that shortest path be P
        #    maybe the longest common starts at P[0]: find longest match P[0:l] in other paths P': KMP, costs O(sum(P' length))
        #                                       P[1]: find longest match P[1:1+l] in other paths P', KMP again, ...
        #
        # total cost is O((min path length)*(sum of path lengths))

        # longest common substring: O(M*N) as far as I know, from KMP + scanning on the other string

        # worst case is to giant paths of size 5e4 such that O(M*N) is 2.5e9, ouch

        # P[0..]: 1. build KMP table on P[0..]
        # then find matches to P[0..] in the other paths, record the max index we got to across all other strings. total O(sum(lengths)) work

        # suppose we ask if there exists a common subpath of length L
        #
        # we could form all L RK hashes on the shortest path
        #    then do set intersection on the size L RK hashes we find among the rest
        #
        # then we can narrow down the largest value of L in log(min path length) operations, each costing O(total path length) time

        # this is feasible.. and also heinous, but whatever. SKIP for now, yikes

        #### new day, new ideas:

        # longest common substring between two:
        #         RK style: get hashes for all L-length strings in shorter one, then scan the longer one and record matches
        #
        #         that takes O(totalSize) time
        #
        #         and then you need to do binary search on L, log(len(shortestPath)) steps
        
        # is there a deterministic one? maybe, but unclear

        # let's try the RK one

        M = max(max(path) for path in paths) + 1
        BIG = (0x7FFFFFFFFFFFFFFF - M*(M-1)) // M # so BIG-1 * M + M*(M-1) doesn't exceed a long

        N = len(paths)
        i = min(range(N), key=lambda i: len(paths[i]))
        if i: paths[i], paths[0] = paths[0], paths[i]

        p = paths[0]
        P = len(p)

        def iter_rk_hashes(path: list[int], L: int) -> Iterator[int]:
            M_pow_BIG = pow(M, L, BIG)
            h = 0
            # Rabin-Karp rolling hash: for ENDING at i the hash is path[i] + M*path[i-1] + ... + M**k * path[i-k] + ...
            for i in range(L):
                h = h*M + path[i]
                h %= BIG

            yield h

            for i in range(L, len(path)):
                h = h*M + path[i]
                h -= M_pow_BIG*path[i-L]
                h = ((h % BIG) + BIG) % BIG # keep mod positive
                yield h

        def check(L: int) -> bool:
            rk_hashes = set(iter_rk_hashes(p, L))
            
            for i in range(1, N):
                rk_hashes &= set(iter_rk_hashes(paths[i], L))
            
            return bool(rk_hashes) # True if 1+ hashes exist, otherwise no

        lo = 0
        hi = P
        while lo < hi:
            L = (lo+hi+1)//2
            if check(L):
                lo = L
            else:
                hi = L-1

        # to verify: we'd need to record canonical indices (first or last) for each hash in p
        #            then when we find a tentative match in a target string we should
        #            iterate over the original chars in p and see if they match the chars in the current path

        return hi
2020