Поиск общих подстрок в нескольких строках

Question

Только пытаюсь учить python. Подскажите пожалуйста библиотеку для python да и вообще в какую сторону рыть для решения задачи по поиску одинаковых сочетаний символов в сравнении 2х и более строк. Под одинаковыми символами подразумевается сочетание 2х и более символов. Например:

Строка 1

54545wqeqweretert545512abcfgdfhfgh54uyi5yuihjkjh5k45454xcv

Строка 2

popowe512abcwql87552453kjkdsfmndsfnsdfsdf5896

В этих 2х разных строках есть одинаковое сочетание символов а именно "512abc", эти сочетания всегда разные и они неизвестны изначально. Их можно обнаружить только после сравнения этих строк. С помощью какой библиотеки python можно решить эту задачу??

Answer 1

Можно по-простому:

Нарезать каждую из строк на n-граммы (фрагменты длиной n)
Сделать из n-грамм множество
Пересечь такие множества для этих двух строк

text1 = "54545wqeqweretert545512abcfgdfhfgh54uyi5yuihjkjh5k45454xcv"
text2 = "popowe512abcwql87552453kjkdsfmndsfnsdfsdf5896"

def get_ngrams(text, min_len=3):
    return set(text[i:i+n] for n in range(min_len, len(text)) for i in range(len(text)-n+1))

print(sorted(list(get_ngrams(text1) & get_ngrams(text2)), key=len, reverse=True))

Вывод:

['512abc', '512ab', '12abc', '512a', '12ab', '2abc', '12a', 'abc', '512', '2ab']

Здесь берутся n-граммы начиная от размера 3 (иначе их слишком много будет). Результат сортируется от самого длинного размера подстроки к короткому.

Answer 2

Задание слишком ёмкое для начинающего (обработка многих строк). Поэтому в качестве примера я переформулировал условие, сделав его менее сложным. Вот готовый скрипт, дальше развивайте его сами:

'''
написать скрипт для решения задачи по поиску одинаковых сочетаний символов (двух и более)
в двух строках. Вывести такие сочетания в виде списка.
'''

import os
def find_common_substrings(str1, str2, min_length=2):
    common_substrings = set()
    len1, len2 = len(str1), len(str2)

    for i in range(len1):
        for j in range(i + min_length, len1 + 1):
            substring = str1[i:j]
            if substring in str2:
                common_substrings.add(substring)

    return list(common_substrings)

# Входные данные
str1 = '54545wqeqweretert545512abcfgdfhfgh54uyi5yuihjkjh5k45454xcv'
str2 = 'popowe512abcwql87552453kjkdsfmndsfnsdfsdf5896'

# Поиск одинаковых сочетаний
common_substrings = find_common_substrings(str1, str2)

# Вывод результата
print("Строка №1:", str1)
print("Строка №2:", str2)
print("Общие сочетания символов:", common_substrings)
os.system("pause")

БЛОГ НА HUSL

Поиск общих подстрок в нескольких строках

Ответы (2 шт):