Поиск наилучшего (а также неполного) вхождения подстроки в строку

From

Max Alekseyev (2:5015/60)

To

Daniil Uspensky

Date

2002-07-02T16:05:04Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Daniil !

Replying to a message of Daniil Uspensky to Ihor.Bobak@nestle.ua:

 DU>>> Ищу сабж, более эффективный, чем последовательный перебор.
 IB>> Что ты имеешь в виду под "наилучшим вхождением подстроки в строку"?

 DU> Например имеется строка abcabacbcabacbbbca, в которой мы ищем
 DU> подстроку bcabacba Наилучшим вхождением будет bcabacb. Или еще можно
 DU> ввести "достаточное" совпадение, т.е. если наилучшее слишком
 DU> трудоемко искать, то ограничиться поискаом первого достаточного.

Это задача называется local alignment (поищи в инете это словосочетание). Решается динамическим программированием.
Можешь еще заглянуть сюда: http://algolist.manual.ru/search/fsearch/index.php

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)