Есть ли способ проверить, содержит ли строка почти другую строку?

Я работаю над проектом, который требует, чтобы я проверял, почти ли строка1 присутствует в строке2, если да (т.е. если она соответствует большему, чем какое-то пороговое соотношение, скажем, дельта), то мне нужно извлечь этот совпавший сегмент из строки2 и сохранить его.

строка1 будет иметь длину от 100 до 200 символов; строка2 будет иметь большую длину в диапазоне от 15000 до 20000 символов.

примеры, которые я сейчас использую

string1 = "MA A NA E LA OO KA A SA A BHA I YA A BA A HA U MA A DA A DA AA NGA GA I KA AA RA A PA A DDA A DA A NA NA A NA TA A RA A BA MA A СА У ДА ЭЭ ГА АА ДЖА А СА А БХА Э ГА Э БА А НА ДА И ТА У"

строка2 = строка2

Я использовал библиотеки fuzzywuzzy и SequenceMatcher в python, но боюсь, что просто могу получить пороговое значение, используя их, но не могу извлечь подстроку из строки2.

from fuzzywuzzy import fuzz
print(fuzz.partial_ratio(string1,string2))

После выполнения нечеткой проверки частичного соотношения для двух строк я получаю отношение 89.

Мне нужно получить (приблизительную) подстроку из строки2, которая должна быть почти такой же длины, как строка1. Это означает, что мне нужно, чтобы 89% совпадали с местоположением строки в string2.


person droidmainiac    schedule 24.04.2019    source источник
comment
Может быть, вы можете найти самую длинную общую подпоследовательность и проверить соотношение?   -  person nice_dev    schedule 24.04.2019
comment
Код fuzzywuzzy является открытым исходным кодом. Кажется тривиальным расширение функции partial_ratio для вывода подстрока, соответствующая наилучшему совпадению (так же, как вы получили бы ">индекс максимального элемента в массиве).   -  person Bernhard Barker    schedule 24.04.2019
comment
@ vivek_23 Это заняло бы слишком много времени, найти все подпоследовательности из обеих строк, а затем сравнить каждую из них.   -  person droidmainiac    schedule 25.04.2019
comment
@Abhijith Поиск LCS так не работает. См. здесь алгоритм.   -  person nice_dev    schedule 25.04.2019