Кто-нибудь встречал такую функцию, которая выполняет тоже самое, что делает strstr но по цепочке буферов?

Здравствуйте, <Аноним>, Вы писали:

А>Кто-нибудь встречал такую функцию, которая выполняет тоже самое, что делает strstr но по цепочке буферов?

Может, просто цикл использовать?

Искомая строка может быть на границе между буферами.

d.4>Может, просто цикл использовать?

Здравствуйте, Аноним, Вы писали:



d.4>>Может, просто цикл использовать?

А>Искомая строка может быть на границе между буферами.

так додумай, алгоритм то тривиальный

А>>Искомая строка может быть на границе между буферами.

DB>так додумай, алгоритм то тривиальный

... и в студию, плиз, как будет готово!

Во-первых не хочется изобретать велосипедов.
А во-вторых, эффективный алгоритм не настолько тривиальный как кажется на 1й взгляд, а какой-нибудь такой:
http://rsdn.ru/article/alg/textsearch.xml

Автор(ы): Андрей Боровский
Дата: 28.01.2002

DB>так додумай, алгоритм то тривиальный

Здравствуйте, Аноним, Вы писали:

А>Кто-нибудь встречал такую функцию, которая выполняет тоже самое, что делает strstr но по цепочке буферов?

std::search умеет всё, были бы итераторы.

RO>std::search умеет всё, были бы итераторы.
тока нифига не оптимально

RO>>std::search умеет всё, были бы итераторы.
А>тока нифига не оптимально

а strstr — верх оптимальности?

TC>а strstr — верх оптимальности?
уж оптимальнее серча. Ибо ищет отнюдь не последовательным перебором.

А>уж оптимальнее серча. Ибо ищет отнюдь не последовательным перебором.

какой же алгоритм у strstr если не последовательный перебор? В оптимизированном виде функция может в определенных условиях сравнивать несколько символов за одну операцию сравнения. Но алгоритм то — тот же. Если исходный буфер большой и искомая подстрока тоже, возможно, имеет смысл использовать какие нибудь более быстрые алгоритмы поиска — например, попробовать boost::regexp. Последний, кстати, может работать с итераторами и можно подсунуть ему какой нибудь самописный контейнер, содержащий фрагментированные данные.

Здравствуйте, TarasCo, Вы писали:

А>>уж оптимальнее серча. Ибо ищет отнюдь не последовательным перебором.

TC>какой же алгоритм у strstr если не последовательный перебор? В оптимизированном виде функция может в определенных условиях сравнивать несколько символов за одну операцию сравнения. Но алгоритм то — тот же. Если исходный буфер большой и искомая подстрока тоже, возможно, имеет смысл использовать какие нибудь более быстрые алгоритмы поиска — например, попробовать boost::regexp. Последний, кстати, может работать с итераторами и можно подсунуть ему какой нибудь самописный контейнер, содержащий фрагментированные данные.

strstr знает, что искомая строка — последовательность символов, которых в алфавите всего 255, так что она может использовать алгоритмы KMP, Boyer—Moore или еще какие-нибудь. std::search тоже могла бы, но обычно не хочет.

Здравствуйте, dcb-BanDos, Вы писали:

А>>Искомая строка может быть на границе между буферами.
DB>так додумай, алгоритм то тривиальный

Какой алгоритм называть тривиальным, вот вопрос.
Если тупой линейный (квадратичный, разумеется) поиск, аналогичный strstr() — то он требует произвольного доступа к тексту (что плохо вяжется с цепочкой буферов — особенно, если она односвязная).
По той же причине здесь неприменим Бойер-Мур.

Если искомая строка зафиксирована, а текст варьируется — то подойдёт Кнут-Моррис-Пратт и другие потоковые алгоритмы.
Если же наоборот, зафиксирован текст — тогда можно было бы предложить построить суффиксное дерево над ним. Но, боюсь, сам факт размещения текста в цепочке буферов значит, что текст большой, и фокус может не пройти...

Здравствуйте, Roman Odaisky, Вы писали:

RO>std::search умеет всё, были бы итераторы.

Были бы соответствующие итераторы (произвольного доступа). Над списками это, как минимум, неоптимально, а то и просто невозможно.

Здравствуйте, <Аноним>, Вы писали:

А>А во-вторых, эффективный алгоритм не настолько тривиальный как кажется на 1й взгляд, а какой-нибудь такой:
А>http://rsdn.ru/article/alg/textsearch.xml

Автор(ы): Андрей Боровский
Дата: 28.01.2002

БМ не подходит. Нужно смотреть КМП.
А вообще, есть замечательная книга Дэна Гасфилда "Строки, суффиксные деревья и последовательности в алгоритмах"
(http://www.ozon.ru/context/detail/id/1393109/)