Нахождение последовательного совпадения подстроки

Question

Я имею в виду две строки;

str1="wild animals are trying to escape the deserted jungle to the sandy island"
str2="people are trying to escape from the smoky mountain to the sandy road"

Чтобы найти соответствие между этими двумя строками, производятся килограммы определенной длины (здесь 10), их хэши и хэши этих двухстроки сравниваются.Скажем, например, если совпадают килограммы из этих двух строк;

['aretryingt', 'etryingtoe', 'ngtoescape', 'tothesandy'] 

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

"aretryingtoescape"  

Заранее благодарю !!!

Answer 1

Сначала создайте себе маску покрытия , состоящую из 0 и 1 (или других символов, если хотите), затем найдите самый длинный пробег 1 с itertools.groupby().

Answer 2

Код, следующий за Идея Игнасио :

#!/usr/bin/env python

from itertools import groupby

str1 = 'wild animals are trying to escape the deserted jungle to the sandy island'
str2 = 'people are trying to escape from the smoky mountain to the sandy road'

words = ['aretryingt', 'etryingtoe', 'ngtoescape', 'tothesandy']

def solve(strings, words):
    s = min([ s.replace(' ', '') for s in strings ], key=len)
    coverage = [False]*len(s)
    for w in words:
        p = s.find(w)
        if p >= 0:
            for i in range(len(w)):
                coverage[p+i] = True
    return max([ ''.join([ y[1] for y in g ]) for k, g in groupby(enumerate(s), key=lambda x: coverage[x[0]]) if k ], key=len)

print solve([str1, str2], words)