Advertisement
alex0sunny

str_subarray

Sep 14th, 2021
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.52 KB | None | 0 0
  1. def find_k_subseq(k, a, b):
  2.     b_subs = set([''.join(map(chr, b[i:i + k])) for i in range(len(b) - k + 1)])
  3.     for i in range(len(a) - k + 1):
  4.         a_sub = ''.join(map(chr, a[i:i + k]))
  5.         if a_sub in b_subs:
  6.             return True
  7.     return False
  8.  
  9.  
  10. def get_len(a, b):
  11.     if len(a) > len(b):
  12.         a, b = b, a
  13.     lo = 0
  14.     hi = len(a) + 1
  15.     while lo < hi - 1:
  16.         mid = (lo + hi) // 2
  17.         if find_k_subseq(mid, a, b):
  18.             lo = mid
  19.         else:
  20.             hi = mid
  21.     return lo
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement