62 lines
1.5 KiB
Python
62 lines
1.5 KiB
Python
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))
|