Usando algoritmos como level-level (levelinstein ou difflib), é fácil encontrar matches aproximados.eg.

>>> import difflib
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio()
0.8571428571428571

As correspondências difusas podem ser detectadas, decidindo um limite conforme necessário.

Requisito atual: encontrar substrings difusas com base em um limite em uma string maior.

por exemplo.

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
#result = "manhatan","manhattin" and their indexes in large_string

Uma solução de força bruta é gerar todas as substrings de comprimento N-1 a N + 1 (ou outro comprimento correspondente), onde N é o comprimento de query_string, e usar levenstein nelas uma a uma e ver o limiar.

Existe uma solução melhor disponível em python, de preferência um módulo incluído no python 2.7, ou um módulo disponível externamente.

ATUALIZAR : O módulo regex do Python funciona muito bem, embora seja um pouco mais lento que o inbuiltre módulo para casos de substring difusa, que é um resultado óbvio devido a operações extras. A saída desejada é boa e o controle sobre a magnitude da imprecisão pode ser facilmente definido.

>>> import regex
>>> input = "Monalisa was painted by Leonrdo da Vinchi"
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE)
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)>