common subarray

Q = 10 ** 9 + 7
R = 2 ** 32


def get_base_hashes(a):
    hashes = [0]
    for v in a:
        hashes.append((hashes[-1] * Q + v) % R)
    return hashes


def calc_hash(i, j, hashes):
    start_part = hashes[i] * pow(Q, (j - i), R)
    return (hashes[j] - start_part) % R


def find_k_subseq(k, a, b, a_hashes, b_hashes):
    for ia in range(len(a) - k + 1):
        a_hash = calc_hash(ia, ia + k, a_hashes)
        for ib in range(len(b) - k + 1):
            b_hash = calc_hash(ib, ib + k, b_hashes)
            if b_hash == a_hash:
                r = k
                for m in range(min(len(a) - ia - k, len(b) - ib - k)):
                    if a[ia + k + m] != b[ib + k + m]:
                        break
                    r += 1
                return r
    return 0


def get_len(a, b):
    if len(a) > len(b):
        a, b = b, a
    a_hashes = get_base_hashes(a)
    b_hashes = get_base_hashes(b)
    lo = 0
    hi = len(a) + 1
    while lo < hi - 1:
        mid = (lo + hi) // 2
        k = find_k_subseq(mid, a, b, a_hashes, b_hashes)
        if k:
            lo = k
        else:
            hi = mid
    return lo


a = [1, 2, 3, 4, 5]
b = [4, 5, 9]
assert (get_len(a, b) == 2)

a = [1, 2, 3, 2, 1]
b = [3, 2, 1, 5, 6]
assert (get_len(a, b) == 3)

assert (get_len([1], [1]) == 1)