Задача нахождения наибольшей общей подпоследовательности, легко решается динамическим программированием:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Но у меня немного другая задача — даже наверное начну с контекста:

Даны две строки: Haystack и Needle
Needle — это точное написание труднопроизносимого слова (это номенклатурные коды, иногда похожие на слова, а иногда нет). Вобщем операторы часто ошибаются вводя их, и на операторов возможности повлиять нету.
Собственно Haystack — это то что набрал оператор. Возможно с ошибками. Но проблема в том, что от оператора приходит не сам код (иначе можно было бы считать расстояние по Дамеро-Левенштейну), а фраза, СОДЕРЖАЩАЯ код где-то посерёдке. Причём окружение кода может быть произвольным, например

Needle = "RX153-alfa";
Haystack = "Client complains about RX153afla, status is red";

Задача распознать что за код пытался ввести оператор.

Для этого у меня созрел план:

1) Найти длиннейшую общую подпоследовательность в строках Haystack и Needle: Common = "RX153aa"
2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
3) Посчитать расстояние Демеро-Левенштейна между Needle и Chunk: damlev("RX153afla","RX153-alfa") = 2; (один инсершн, и одна транспозиция) ну и соотнести с длинной Needle, вычтя полученное соотношение из 1.

Ну и отсортировать коды, по этому критерию. В каждый конкретный момент кодов не много, около 1000. Но они добавляются и удаляются.

Типа FUZZYCONTAINS(Haystack,Needle) = 1-DamLev(Chunk(Haystack,Common(Haystack,Needle)))/LEN(Needle)

И вот всё у меня вроде есть, кроме второго шага.
Как найти кратчайшую подстроку содержащую заданную подпоследовательность.
Что моё динамически-прогрммное мышление сломалось на этой задаче.
Я не вижу чего-то?
Решение за n*m*n*m — элементарное,
за n*n*m — возможно сейчас добью, но это плохо,
Товарищи, как это распилить за O(n*m) ?