最长公共子路径

/*
 * Solution Approach with Java Stream:
 * 1. Use binary search to find the maximum length of the common subpath.
 * 2. For each possible length, check if there is a common subpath by maintaining a set of hash values.
 * 3. Use streams to perform set operations for each path.
 */

import java.util.*;
import java.util.stream.Collectors;

public class SolutionStream {
    public int longestCommonSubpath(int n, int[][] paths) {
        int left = 1, right = Arrays.stream(paths).mapToInt(p -> p.length).min().getAsInt();

        long mod = (1L << 61) - 1;
        long base = 1000000007;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (hasCommonSubpath(paths, mid, mod, base)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    private boolean hasCommonSubpath(int[][] paths, int length, long mod, long base) {
        Set<Long> commonHashes = null;

        for (int[] path : paths) {
            Set<Long> currentHashes = new HashSet<>();
            long hash = 0, power = 1;

            for (int i = 0; i < length; i++) {
                hash = (hash * base + path[i]) % mod;
                power = (power * base) % mod;
            }
            currentHashes.add(hash);

            for (int i = length; i < path.length; i++) {
                hash = (hash * base + path[i] - path[i - length] * power % mod + mod) % mod;
                currentHashes.add(hash);
            }

            if (commonHashes == null) {
                commonHashes = currentHashes;
            } else {
                commonHashes.retainAll(currentHashes);
                if (commonHashes.isEmpty()) return false;
            }
        }
        return !commonHashes.isEmpty();
    }
}