def longest_common_len_naive(strs, k):
    s0 = strs[0]
    best = 0
    for i in range(len(s0)):
        for j in range(i + 1, len(s0) + 1):
            sub = s0[i:j]
            cnt = 0
            for s in strs:
                if sub in s:
                    cnt += 1
            if cnt >= k and j - i > best:
                best = j - i
    return best


def longest_common_len_optimized(strs, k):
    import sys

    def has_len(L):
        if L == 0:
            return True
        base = 911382323
        mod = 10**9 + 7
        powL = pow(base, L - 1, mod)
        commons = None
        for s in strs:
            if L > len(s):
                return False
            h = 0
            st = set()
            for t in range(L):
                h = (h * base + ord(s[t])) % mod
            st.add(h)
            for t in range(L, len(s)):
                h = (h - ord(s[t - L]) * powL) % mod
                h = (h * base + ord(s[t])) % mod
                st.add(h)
            if commons is None:
                commons = st
            else:
                commons &= st
            if not commons:
                return False
        return len(commons) >= k

    lo, hi = 0, min(len(s) for s in strs)
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if has_len(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans


if __name__ == "__main__":
    strs = ["abracadabra", "cadabracad", "dabrac"]
    print(longest_common_len_naive(strs, 2))
    print(longest_common_len_optimized(strs, 2))