LINUX.ORG.RU

Интерфейс для алгоритма поиска

 ,


0

6

Здравствуйте. Имеется дилема по поводу интерфейса для алгоритма поиска.

Итак, есть std::search. Он ищет подстроку в строке. И возвращает итератор на первое совпадение. Если мы хотим следующее вхождение, то просто передаём другой диапазон.

Что имеется в Boost.Algorithm - есть реализация алгоритма Бойера-Мура. Раньше он тоже возвращал итератор на первый найденный элемент. Теперь он возвращает пару итераторов (начало надйенного паттерна, конец найденного паттерна).

Но проблема в том, что Бойер-Мур возвращает итераторы только на первый найденный элемент. Чтобы найти все вхождения подстроки в строку, мы можем должны вызвать N раз. Накладных расходов на предпросчёт при каждом вызове нет - мы можем создать обьект Boyer-Moore, и только при создании будут рассчитаны две таблицы.

Проблема в том, что при поиске подстроки Бойер-Мур использует умный сдвиг по входной строке, и если мы будем вызывать N раз функцию поиска, эта информация о сдвиге будет теряться, и производительность будет проседать. Если мы хотим посчитать все вхождения подстроки в строку, то быстрее будет не N раз вызывать функцию, а за 1 раз найти все вхождения.

Но тогда придётся плодить какой-то новый интерфейс: один для нахождения первого вхождения, второй для нахождения всех вхождений.

Как будет лучше поступить здесь?

Не обязательно делать несколько интерфейсов, достаточно одного объекта-состояния который будет иницилизироваться диапазоном и метод поиска. Вроде...

search state(begin, end);

while (auto next = state()) {

}

if (auto first = search(begin, end)()) {

}

mashina ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.