Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def find_k_subseq(k, a, b):
- b_subs = set([''.join(map(chr, b[i:i + k])) for i in range(len(b) - k + 1)])
- for i in range(len(a) - k + 1):
- a_sub = ''.join(map(chr, a[i:i + k]))
- if a_sub in b_subs:
- return True
- return False
- def get_len(a, b):
- if len(a) > len(b):
- a, b = b, a
- lo = 0
- hi = len(a) + 1
- while lo < hi - 1:
- mid = (lo + hi) // 2
- if find_k_subseq(mid, a, b):
- lo = mid
- else:
- hi = mid
- return lo
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement