3妹

3妹：2哥，昨晚台湾省发生6.5级地震了
2哥：嗯，看到了，今年国家真是多灾多难，四川省刚地震不久，台湾省又地震了。
3妹：是啊，现在还没报出有人员伤亡。
2哥：但愿大家都没事，山河无恙。
3妹：2哥，今天周日了，准备干什么去呀？
2哥：还是呆在家里吧，梅花台风刚过，出去太热了。
3妹：我也不想出去，懒的动。
2哥：不出去陪男朋友逛街吗？
3妹：2哥烦人，明知道我还是单身狗🐶，不理你了。

讲课

题目：

一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。

总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现，但同一个城市在一条路径中不会连续出现。

给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 0 。

一个 子路径 指的是一条路径中连续的城市序列。

示例 1：

输入：n = 5, paths = [[0,1,2,3,4],
[2,3,4],
[4,0,1,2,3]]
输出：2
解释：最长公共子路径为 [2,3] 。
示例 2：

输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有公共子路径。
示例 3：

输入：n = 5, paths = [[0,1,2,3,4],
[4,3,2,1,0]]
输出：1
解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。

提示：

1 <= n <= 105
m == paths.length
2 <= m <= 105
sum(paths[i].length) <= 105
0 <= paths[i][j] < n
paths[i] 中同一个城市不会连续重复出现。

java代码：

class Solution {
    public int longestCommonSubpath(int n, int[][] paths) {
        int minLen = Integer.MAX_VALUE; for(int[] path : paths) minLen = Math.min(minLen, path.length);
        int lft = 1, rht = minLen, mid, ans = 0;
        while(lft <= rht) {
            mid = lft + (rht - lft) / 2;
            if(check(paths, mid)) {
                ans = mid;
                lft = mid + 1;
            }
            else {
                rht = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int[][] paths, int len) {
        long mod = Integer.MAX_VALUE, base1 = 100007, mult1 = 1L, base2 = 100009, mult2 = 1L;
        for(int i = 1; i <= len; ++i) {
            mult1 = mult1 * base1 % mod;
            mult2 = mult2 * base2 % mod;
        }
        Map<Long, Set<Long>> map1 = new HashMap<>();
        for(int i = 0; i < paths.length; ++i) {
            long key = 0L, val = 0L;
            for(int j = 0; j < len; ++j) {
                key = (key * base1 + paths[i][j]) % mod;
                val = (val * base2 + paths[i][j]) % mod;
            }
            Map<Long, Set<Long>> map2 = new HashMap<>();
            if(i == 0 || map1.containsKey(key) && map1.get(key).contains(val)) {
                if(!map2.containsKey(key)) map2.put(key, new HashSet<Long>());
                map2.get(key).add(val);
            }
            for(int j = len; j < paths[i].length; ++j) {
                key = ((key * base1 - (paths[i][j - len]) * mult1 + paths[i][j]) % mod + mod) % mod;
                val = ((val * base2 - (paths[i][j - len]) * mult2 + paths[i][j]) % mod + mod) % mod;
                if(i == 0 || map1.containsKey(key) && map1.get(key).contains(val)) {
                    if(!map2.containsKey(key)) map2.put(key, new HashSet<Long>());
                    map2.get(key).add(val);
                }
            }
            if(map2.isEmpty()) return false;
            map1 = map2;
        }
        return true;
    } 
}