1923. Longest Common Subpath

There is a country of n cities numbered from 0 to n - 1. In this country, there is a road connecting every pair of cities.

There are m friends numbered from 0 to m - 1 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 more than once, but the same city will not be listed consecutively.

Given an integer n and a 2D integer array paths where paths[i] is an integer array representing the path of the ith friend, return the length of the longest common subpath that is shared by every friend’s path, or 0 if there is no common subpath at all.

A subpath of a path is a contiguous sequence of cities within that path.

class Solution {
public:
    int longestCommonSubpath(int n, vector<vector<int>>& A) {
        int l = 0, r = min_element(begin(A), end(A), [](vector<int>& a, vector<int>& b) {return a.size() < b.size();})->size();
        long long base = 1010101, mod = 1e11 + 19;
        while(l < r) {
            int m = (l + r + 1) / 2;
            unordered_set<long long> us;
            for(int i = 0; i < A.size() and (i == 0 or !us.empty()); i++) {
                long long hash = 0, d = 1;
                unordered_set<long long> nus;
                for(int j = 0; j < A[i].size(); j++) {
                    hash = (hash * base + A[i][j]) % mod;
                    if(j >= m) {
                        hash = (hash + mod - d * A[i][j - m] % mod) % mod;
                    } else {
                        d = d * base % mod;
                    }
                    if(j >= m - 1 and (i == 0 or us.count(hash))) {
                        nus.insert(hash);
                    }
                }
                swap(us, nus);
            }

            if(us.empty()) r = m - 1;
            else l = m;
        }
        return l;
    }
};