Дополнительная проблема в том что строка для поиска составная, т.е. в одной позиции буквы может быть больше одного символа,
нужно найти максимально длинное общее совпадение, например:
dATIS
thimATIS : найдено совпадение 4-рех символов
На текущий момент найдено решение, которое позволяет найти совпадения примерно за O(nm) времени , это не устраивает, т.к. в реальном применении база эталонных строк будет в районе 4 млн. записей, каждая запись ~50 символов, количество сложных строк для поиска 4-6 тыс на запрос (длинна 150 символов),
плюс дополнительная обработка каждого результата поиска тестовой строки, итого оценка требуемых операций несколько десятков террафлопс...
Нужно найти линейный алгоритм поика, может кто-нибудь знает, в каком направлении копать?
