Нечеткий поиск подстроки в строке

Здравствуйте. Необходимо реализовать на Java поиск подстроки в строке. Т.е. строка "Разница между родившимися и умершими" должна быть найдена в строке "Разность между числом родившихся и числом умерших за определенное время (например, за один год) называют естественным приростом населения."
А строка "Ивановыми" должна быть найдена в строке "Иванов - древнейший житель города"
Необходим лишь ответ - есть ли что-то похожее в строке. Посоветуйте что-нибудь, желательно уже реализованное на Java.

Ответ

Грубо говоря это делается в 3 шага:
Разбиваем строку на лексемы/слова Полученные лексемы прогоняем через Apache Lucene c русской морфологией - в итоге получаем список лексем очищенный от падежных/родовых и прочих морфологичечких признаков характерных для великого могучего, то есть вместо:
Разность между числом родившихся и числом умерших за определенное время
получим
Разница между число родить и число умереть за определенный время
Далее для этих лексем вычисляем хэш функцию умеющую выдавать близкие значения хэша для похожих слов - например SimHash или что-то вроде упомянутого Левенштейна
Остальное надеюсь объяснять не надо.