поиск максимально похожей подстроки

[trympyrym]

День добрый!

Задача такова: при данном тексте ($TEXT$) длины $n$ и данном образце ($SAMPLE$) длины $m$ найти позицию $i$, минимизирующую расстояние по Хэммингу между $SAMPLE$ и $TEXT[i : i + (m - 1)]$.

Причем сделано должно быть это либо сильно сокращенным перебором (сложность $\alpha n^2$, где $\alpha < \frac {1} {50}$), либо с линейно-логарифмической сложностью.

Особенность задачи - мощность алфавита $\left|S\right| << m$

Алгоритмы точного поиска не помогают, ибо перебирать все варианты $SAMPLE$ с ошибками очень долго.

Алгоритмы нечеткого поиска (те, что я смог найти) решают несколько другую задачу - они находят подстроки $TEXT$, расстояние по Хэммингу от которых до $SAMPLE$ не превосходит некоторой константы $K$. Мне это тоже не подходит, ибо при $K \approx L$ (а такое в моей задаче вполне реализуемо) их сложность вырождается до квадратичной.

Я в тупике. Подскажите, пожалуйста, какой алгоритм использовать мне следует.

[Pavia]

trympyrym
Алгоритмов море выбирайте, тот который вам больше подходит.

1) К примеру автомат сложность поиска будет $O(N)$, решение точное.
2) Через свёртку(корреляцию) в худшем случае $O(N*Log(N))$ в лучшем $O(N)$ решение использует другую метрику.
3) Случайным образом выбирать смещение образца, так что бы $\alpha < \frac {1} {50}$
4) Использовать отсечения на основе признаков. Признаки надо под конкретную задачу подбирать самому. Подход творческий.

[trympyrym]

Pavia в сообщении #785698 писал(а):

trympyrym
Алгоритмов море выбирайте, тот который вам больше подходит.

Да, действительно, есть море алгоритмов, в описании которых есть слова "строка" и "подстрока". В первом посте как раз описано, почему приведенные Вами подходы (кроме, разве что, 4-го) неприменимы к моей задаче. В любом случае спасибо за ответ