КМП, БМ. Проникните в суть, модифицируйте.

LCS?

спасибо что закидали меня абривеатурами :) КМП ищет точную подстроку в строке, БМ вообще не нашел, но подозреваю что тоже.

Пойдет?

http://ru.wikipedia.org/wiki/Longest_common_substring

//лень разлогиниваться

Вы измеряете длину строк в словах. Значит ли это, что вы оперируете только целыми словами или просто длина так выражена приблизительно?

agrep - text search tool with support for approximate patterns

да, две строки на естественном языке. Одна короткая другая длинная. Конечно меня интересуют целые слова, но они могут быть в разном порядке или в разных формах.

построить индекс по всем вариантам слов (для разных форм одного слова использовать один id) задача сведется к поиску подмножества int-ов

да, я так изначально и предполагал, используя pymorphy находить инфинитивы... Но вдруг есть способ попроще? :)

>да, я так изначально и предполагал, используя pymorphy находить инфинитивы... Но вдруг есть способ попроще? :)

Если вы оперируете на уровне лексем и не ниже, «алгоритм попроще» для строк максимум в 20 лексем может оказаться писать сложнее, чем профиту будет с него.

Можно разве что какие-нибудь оптимизации провести. Вывести какие-нибудь правила типа «X и Y не могут быть формами одной лексемы, если у них не совпадают первые n символов» и ускорить поиск предварительной проверкой. Но это все мелочи.

Может быть, можно придумать набор простых правил для конкретного словаря/множества слов.

Впрочем, может быть, кто-то и знает более простой способ.

Хм.. ну, если я правильно понял, то необходима необходима некая эвристика (тем более, что мера сходства не указана).

Определим меру различия двух слов как минимальное количество операций, которые нужно применить к слову A, чтобы получить слово B. Операции: удалить символ, записать лишний симво, заменить символ на другой.

Для слов A и B считается динамикой значение f(len A, len B):

f(n, k) = min { f(n-1, k) + 1, f(n, k-1) + 1, f(n-1, k-2)*(An==Bk) + (f(n-1, k-2) + 1)*(An!=Bk) }

Меру различия можешь потом нормировать по длинне слова, хз. Потом каждому слову из мелкой подстроки ищешь найболее подходящее, например. Где-то так.

Для строк в 20 слов должно быть нормально.