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

Я хотел бы сравнить 2 строки и сохранить соответствие, отделив место, где сравнение не удается.

Так что, если у меня есть 2 строки –

string1 = apples string2 = appleses answer = apples 

Другой пример, поскольку строка может содержать более одного слова.

 string1 = apple pie available string2 = apple pies answer = apple pie 

Я уверен, что есть простой способ Python сделать это, но я не могу это исправить, любая помощь и объяснение оценены.

  • Поиск n-го наименьшего числа в списке?
  • Сравнение / объединение двух словарей
  • Python: удаление элемента в sys.path отменяется каждый раз, когда я перезапускаю интерпретатор
  • Как использовать строковое значение в качестве имени переменной в Python?
  • как добавить разделитель тысяч в число, которое было преобразовано в строку в python?
  • Python: нажатие кнопки
  • Python: самый быстрый способ обработки большого файла
  • Как получить все смежные подстроки строки в Python?
  • 9 Solutions collect form web for “Найти общую подстроку между двумя строками”

    Его называют самой длинной общей проблемой подстроки. Здесь я представляю простое, понятное, но неэффективное решение. Для получения правильного вывода для больших строк потребуется много времени, так как сложность этого алгоритма равна 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") 
    Interesting Posts

    Список всех файлов в онлайн-каталоге с Python?

    Как создать 2D-список списков int и установить определенные значения

    Получение следующего элемента при циклическом перемещении по списку

    Почему кортеж (set ()) == tuple (set ()) 85% времени с включенной хэш-рандомизацией?

    привязки python gstreamer для окон

    Динамическое программирование для примитивного калькулятора

    Каков наиболее эффективный способ установки строк в нули для разреженной матрицы scipy?

    Ошибка Python 3.1 и Sublime Text 2

    Как выполнять транзакции базы данных с помощью psycopg2 / python db api?

    Как передать параметры в драйвер Selenium Chrome с помощью Python?

    Изменение python по умолчанию на другую версию

    Ограничение значений параметров командной строки

    Должны ли Python unittests быть в отдельном модуле?

    Регулярное выражение Python: сопоставление скобок в скобках

    Использовать итератор как имя переменной в цикле питона

    Python - лучший язык программирования в мире.