Список строк, получить общую подстроку из n элементов, Python

Question

Моя проблема может быть похожа на this, но другая ситуация. Рассмотрим этот список на входе:

['ACCCACCCGTGG','AATCCC','CCCTGAGG'] 

А другой вход п, п представляет собой число, размерность подстроки общего в каждом элементе списка. Таким образом, выходной сигнал должен быть максимально occorence подстрока с числом occorences, похожее на это:

{'CCC' : 4} 

4 becouse в первом элементе списка дважды, и один раз в двух других строк. CCC becouse является longhest подстроки с 3-х элементов, которая повторяется по крайней мере 1 раз в строке я начал таким образом:

def get_n_repeats_list(n,seq_list): 
max_substring={} 
list_seq=list(seq_list) 
for i in range(0,len(list_seq)): 
    if i+1<len(list_seq): 
     #Idea : to get elements in common,comparing two strings at time 
     #in_common=set(list_seq[i])-set(list_seq[i+1]) 
     #max_substring...  
return max_substring 

Может быть здесь solution

Answer 1

Итак, это мое занятие. Это определенно не самая красивая вещь на планете, но она должна работать нормально.

a = ['ACCCWCCCGTGG', 'AATCCC', 'CCCTGAGG'] 

def occur(the_list, a_substr): 
    i_found = 0 
    for a_string in the_list: 
     for i_str in range(len(a_string) - len(a_substr) + 1): 
      #print('Comparing {:s} to {:s}'.format(substr, a_string[i_str:i_str + len(substr)])) 
      if a_substr == a_string[i_str:i_str + len(a_substr)]: 
       i_found += 1 
    return i_found 

def found_str(original_List, n): 
    result_dict = {} 
    if n > min(map(len, original_List)): 
     print("The substring has to be shorter than the shortest string!") 
     exit() 
    specialChar = '|' 
    b = specialChar.join(item for item in original_List) 
    str_list = [] 
    for i in range(len(b) - n): 
     currStr = b[i:i+n] 
     if specialChar not in currStr: 
      str_list.append(currStr) 
     else: 
      continue 
    str_list = set(str_list) 

    for sub_strs in str_list: 
     i_found = 0 
     for strs in original_List: 
      if sub_strs in strs: 
       i_found += 1 

     if i_found == len(original_List): 
      #print("entered with sub = {:s}".format(sub_strs)) 
      #print(occur(original_List, sub_strs)) 
      result_dict[sub_strs] = occur(original_List, sub_strs) 

    if result_dict == {}: 
     print("No common substings of length {:} were found".format(n)) 

    return result_dict 

end = found_str(a, 3) 
print(end) 

возвращается: { 'CCC': 4}

Answer 2

def long_substr(data): 
    substr = '' 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and is_substr(data[0][i:i+j], data): 
        substr = data[0][i:i+j] 
    return substr  

def is_substr(find, data): 
    if len(data) < 1 and len(find) < 1: 
     return False 
    for i in range(len(data)): 
     if find not in data[i]: 
      return False 
    return True 

input_list = ['A', 'ACCCACCCGTGG','AATCCC','CCCTGAGG'] 
longest_common_str = long_substr(input_list) 

if longest_common_str: 
    frequency = 0 
    for common in input_list: 
     frequency += common.count(longest_common_str) 

    print (longest_common_str, frequency)  
else: 
    print ("nothing common")   

Выход

A 6

Answer 3

import operator 
LL = ['ACCCACCCGTGG','AATCCC','CCCTGAGG'] 

def createLenList(n,LL): 
    stubs = {} 
    for l in LL: 
     for i,e in enumerate(l): 
      stub = l[i:i+n]   
      if len(stub) == n: 
      if stub not in stubs: stubs[stub] = 1 
      else:     stubs[stub] += 1 

    maxKey = max(stubs.iteritems(), key=operator.itemgetter(1))[0] 
    return [maxKey,stubs[maxKey]] 

maxStub = createLenList(3,LL) 
print maxStub