最优路径算法例题（最长公共子路径）
最优路径算法例题（最长公共子路径）示例 1：一个 子路径 指的是一条路径中连续的城市序列。一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现，但同一个城市在一条路径中不会连续出现。给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 0 。
#头条创作挑战赛#
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] 中同一个城市不会连续重复出现。
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;
}
}
