Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
31 lines (23 sloc) 560 Bytes
def substr_in_all(arr, part):
for dna in arr:
if dna.find(part)==-1:
return False
return True
def common_substr(arr, l):
first = arr[0]
for i in range(len(first)-l+1):
part = first[i:i+l]
if substr_in_all(arr, part):
return part
return ""
def longest_common_substr(arr):
l = 0; r = len(arr[0])
while l+1<r:
mid = (l+r) / 2
if common_substr(arr, mid)!="":
l=mid
else:
r=mid
return common_substr(arr, l)
arr=['abdercaagcd','decaaagcaeder','acderaacdgg']
print longest_common_substr(arr)
You can’t perform that action at this time.