Найти общую подстроку между двумя строками

Его называют самой длинной общей проблемой подстроки. Здесь я представляю простое, понятное, но неэффективное решение. Для получения правильного вывода для больших строк потребуется много времени, так как сложность этого алгоритма равна O (N ^ 2).

 def longestSubstringFinder(string1, string2): answer = "" len1, len2 = len(string1), len(string2) for i in range(len1): match = "" for j in range(len2): if (i + j < len1 and string1[i + j] == string2[j]): match += string2[j] else: if (len(match) > len(answer)): answer = match match = "" return answer print longestSubstringFinder("apple pie available", "apple pies") print longestSubstringFinder("apples", "appleses") print longestSubstringFinder("bapples", "cappleses") 

Вывод

 apple pie apples apples 

Для полноты, difflib в стандартной библиотеке предоставляет множество утилит сравнения последовательностей. Например, find_longest_match который находит самую длинную общую подстроку при использовании в строках. Пример использования:

 from difflib import SequenceMatcher string1 = "apple pie available" string2 = "come have some apple pies" match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2)) print(match) # -> Match(a=0, b=15, size=9) print(string1[match.a: match.a + match.size]) # -> apple pie print(string2[match.b: match.b + match.size]) # -> apple pie 

 def common_start(sa, sb): """ returns the longest common substring from the beginning of sa and sb """ def _iter(): for a, b in zip(sa, sb): if a == b: yield a else: return return ''.join(_iter()) 

 >>> common_start("apple pie available", "apple pies") 'apple pie' 

Или немного страннее:

 def stop_iter(): """An easy way to break out of a generator""" raise StopIteration def common_start(sa, sb): ''.join(a if a == b else stop_iter() for a, b in zip(sa, sb)) 

Что может быть более читаемым, поскольку

 def terminating(cond): """An easy way to break out of a generator""" if cond: return True raise StopIteration def common_start(sa, sb): ''.join(a for a, b in zip(sa, sb) if terminating(a == b)) 

Пытаться:

 import itertools as it ''.join(el[0] for el in it.takewhile(lambda t: t[0] == t[1], zip(string1, string2))) 

Это сравнение с началом обеих строк.

Это не самый эффективный способ сделать это, но это то, что я мог придумать, и это работает. Если кто-то может его улучшить, пожалуйста. Что он делает, так это делает матрицу и ставит 1, где совпадают символы. Затем он сканирует матрицу, чтобы найти самую длинную диагональ 1 с, отслеживая, где она начинается и заканчивается. Затем он возвращает подстроку входной строки с начальным и конечным позициями в качестве аргументов.

Примечание. Это находит только одну самую длинную общую подстроку. Если есть более одного, вы можете создать массив для хранения результатов и вернуть его. Кроме того, он чувствителен к регистру, поэтому (Apple pie, apple pie) вернет pple pie.

 def longestSubstringFinder(str1, str2): answer = "" if len(str1) == len(str2): if str1==str2: return str1 else: longer=str1 shorter=str2 elif (len(str1) == 0 or len(str2) == 0): return "" elif len(str1)>len(str2): longer=str1 shorter=str2 else: longer=str2 shorter=str1 matrix = numpy.zeros((len(shorter), len(longer))) for i in range(len(shorter)): for j in range(len(longer)): if shorter[i]== longer[j]: matrix[i][j]=1 longest=0 start=[-1,-1] end=[-1,-1] for i in range(len(shorter)-1, -1, -1): for j in range(len(longer)): count=0 begin = [i,j] while matrix[i][j]==1: finish=[i,j] count=count+1 if j==len(longer)-1 or i==len(shorter)-1: break else: j=j+1 i=i+1 i = i-count if count>longest: longest=count start=begin end=finish break answer=shorter[int(start[0]): int(end[0])+1] return answer 

То же, что и Evo , но с произвольным количеством строк для сравнения:

 def common_start(*strings): """ Returns the longest common substring from the beginning of the `strings` """ def _iter(): for z in zip(*strings): if z.count(z[0]) == len(z): # check all elements in `z` are the same yield z[0] else: return return ''.join(_iter()) 

Возвращает первую длинную общую подстроку:

 def compareTwoStrings(string1, string2): list1 = list(string1) list2 = list(string2) match = [] output = "" length = 0 for i in range(0, len(list1)): if list1[i] in list2: match.append(list1[i]) for j in range(i + 1, len(list1)): if ''.join(list1[i:j]) in string2: match.append(''.join(list1[i:j])) else: continue else: continue for string in match: if length < len(list(string)): length = len(list(string)) output = string else: continue return output 

Сначала вспомогательная функция, адаптированная из парного рецепта itertools для создания подстрок.

 import itertools def n_wise(iterable, n = 2): '''n = 2 -> (s0,s1), (s1,s2), (s2, s3), ... n = 3 -> (s0,s1, s2), (s1,s2, s3), (s2, s3, s4), ...''' a = itertools.tee(iterable, n) for x, thing in enumerate(a[1:]): for _ in range(x+1): next(thing, None) return zip(*a) 

Затем функция выполняет итерацию над подстроками, наиболее долгое время и тесты для членства. (эффективность не учитывается)

 def foo(s1, s2): '''Finds the longest matching substring ''' # the longest matching substring can only be as long as the shortest string #which string is shortest? shortest, longest = sorted([s1, s2], key = len) #iterate over substrings, longest substrings first for n in range(len(shortest)+1, 2, -1): for sub in n_wise(shortest, n): sub = ''.join(sub) if sub in longest: #return the first one found, it should be the longest return sub s = "fdomainster" t = "exdomainid" print(foo(s,t)) 

 >>> domain >>> 

Исправить ошибки с первым ответом:

 def longestSubstringFinder(string1, string2): answer = "" len1, len2 = len(string1), len(string2) for i in range(len1): for j in range(len2): lcs_temp=0 match='' while ((i+lcs_temp < len1) and (j+lcs_temp<len2) and string1[i+lcs_temp] == string2[j+lcs_temp]): match += string2[j+lcs_temp] lcs_temp+=1 if (len(match) > len(answer)): answer = match return answer print longestSubstringFinder("dd apple pie available", "apple pies") print longestSubstringFinder("cov_basic_as_cov_x_gt_y_rna_genes_w1000000", "cov_rna15pcs_as_cov_x_gt_y_rna_genes_w1000000") print longestSubstringFinder("bapples", "cappleses") print longestSubstringFinder("apples", "apples")