Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

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

P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

Попробуй std::search, предикат для сравнения без учета регистра вроде был в boost-е.

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

P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

std::search со своим предикатом.

Вот только "не медленнее" тут не катит — другая ситуация.
Подводный камень — наборы символов, которые необходимо обрабатывать
(если только латиница — куда ни шло, если любые — попадалово
с кодировками).

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

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

P>>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

_wf>std::search со своим предикатом.

_wf>Вот только "не медленнее" тут не катит — другая ситуация.
_wf>Подводный камень — наборы символов, которые необходимо обрабатывать
_wf>(если только латиница — куда ни шло, если любые — попадалово
_wf>с кодировками).

не, это понятно. кодировка только asc-ii

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

P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией.

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

P>>>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
P>не, это понятно. кодировка только asc-ii

А почему "asc-ii", если это официально называется ASCII?

Вообще, когда встаёт вопрос о "не медленнее", это означает две вещи:
1) Хочется избежать велосипедов со сложностью, заведомо большей чем оригинальный алгоритм.
2) Профайлер наблюдает просадку именно в этом месте.

strstr сам по себе не быстрый — в угоду O(1) памяти он тратит O(n^2) времени. (равно как std::search)
Если "strIstr" на его основе не устраивает, то, скорее всего, не устроит и сам strstr. Тогда это повод задуматься о скоростных алгоритмах поиска.

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

D>переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией.

предварительно скопировав строку и строку поиска

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>предварительно скопировав строку и строку поиска
ну и что даже так, хотя конечно можно и дешевле если писать самому.

делов то на 3 копейки :

#include <stdio.h>
#include <string.h>
#include <ctype.h>
char * ustrstr( const char *source, const char *word )
{ 
    const char *bp = word;
    const char *back_pos;
    while( *source != 0 && source != 0 && word != 0 )
    {
        back_pos = source;
        while( toupper(*back_pos++) == toupper(*word++) ) 
        { 
            if( *word == 0 ) 
            {
                return (char*)(back_pos-strlen(bp));
            }
        }
        ++source;
        word = bp; 
    }
    return 0;
}

возможно надо отладить.

_wf>std::search со своим предикатом.
_wf>Вот только "не медленнее" тут не катит — другая ситуация.
_wf>Подводный камень — наборы символов, которые необходимо обрабатывать
_wf>(если только латиница — куда ни шло, если любые — попадалово
_wf>с кодировками).
std::search — просто поиск линейный перебором, плата за итерируемость без random access
а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php

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

P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?

CompareString Function

--------------------------------------------------------------------------------

Compares two character strings, using the specified locale.

Syntax

int CompareString( LCID Locale,
DWORD dwCmpFlags,
LPCTSTR lpString1,
int cchCount1,
LPCTSTR lpString2,
int cchCount2
);

dwCmpFlags

NORM_IGNORECASE
Ignore case. The Remarks section below explains how this differs from LINGUISTIC_IGNORECASE.

А вот будет ли она не медленнее strstr — не знаю. Вряд ли. Думаю, у нее хватит ума делать преобразование к одному регистру символов по текущей локали, то есть не быстро.

_wf>>std::search со своим предикатом.
_wf>>Вот только "не медленнее" тут не катит — другая ситуация.
_wf>>Подводный камень — наборы символов, которые необходимо обрабатывать
_wf>>(если только латиница — куда ни шло, если любые — попадалово
_wf>>с кодировками).
O>std::search — просто поиск линейный перебором, плата за итерируемость без random access
O>а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php
Кто несогласен — идут читать документацию по std::search, и особенно следующее:
It evaluates the predicate (last2 — first2) * (last1 — first1) times, at most.
что соотвествует самому медленному методу (то бишь прямому перебору) из приведенной мной ссылки

O>>std::search — просто поиск линейный перебором, плата за итерируемость без random access
O>>а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php
O>Кто несогласен — идут читать документацию по std::search, и особенно следующее:
O>It evaluates the predicate (last2 — first2) * (last1 — first1) times, at most.
O>что соотвествует самому медленному методу (то бишь прямому перебору) из приведенной мной ссылки

для особо принципиально несогласных, прогоните след код на вашем компиляторе:

    std::string haystack, needle;
    haystack.resize(0x10000, 'x');
    needle.resize(0x1000, 'y');
    DWORD ticks0 = ::GetTickCount();
    for (int i=0;i<10000; i++)
    {
        std::search(haystack.begin(), haystack.end(), needle.begin(), needle.end());
    }
    DWORD ticks1 = ::GetTickCount();
    for (int i=0;i<10000; i++)
    {
        haystack.find(needle);
    }
    DWORD ticks2 = ::GetTickCount();
    printf("%u msec %u msec\n", ticks1-ticks0, ticks2-ticks1);

студия 2005. дефолтовый релиз по скорости у меня дал след результаты: 1828 msec 437 msec

Здравствуйте, ononim, Вы писали:
O>студия 2005. дефолтовый релиз по скорости у меня дал след результаты: 1828 msec 437 msec

Вся разница в том, что это лучшее из того что здесь есть, это понятно ?
т.к это единственное "ЗДЕСЬ" решение которое основывается не на словах а которое работает.
Напишите свою версию и пожалуйста показывайте цифры. А сравнивать функцию которая не учитывает регистр и с той которая учитывает не корректно для оценки ее произоводительности.

D>Здравствуйте, ononim, Вы писали:
O>>студия 2005. дефолтовый релиз по скорости у меня дал след результаты: 1828 msec 437 msec
D>Вся разница в том, что это лучшее из того что здесь есть, это понятно ?
D>т.к это единственное "ЗДЕСЬ" решение которое основывается не на словах а которое работает.
D>Напишите свою версию и пожалуйста показывайте цифры. А сравнивать функцию которая не учитывает регистр и с той которая учитывает не корректно для оценки ее произоводительности.
То есть вы предлагаете мне написать на халяву код?
Я привел список алгоритмов оптимизированного поиска подстрок, с описанием их различий (оптимизация по памяти, времени, размеру строк etc).
Разница их реализаций будет отличаться от грубого перебора в разы и даже на порядки — в зависимости от того на каких данных хочет их гонять автор. Возможно они уже реализованы в том же бусте — я хз. Но я точно знаю что std::search будет медленнее любого из этих алгоритмов, и, в частности, будет медленнее чем strstr которая обычно использует один из этих оптимизированных алгоритмов. Писать код по описанию алгоритма или искать готовую реализацию в гугле — этим пусть занимается топикстартер или тот кому делать нечего.

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

PD>CompareString Function

Эта функция мне известна, но беда в том что для ее использования нужно писать цикл.

Мне нужнен полный аналог strstr, сам пробегающий всю строку до нулевого символа, и возвращающий указатель на вхождение подстроки.
например когда в заголовке HTTP ответа нужно найти строку типа "Content-Length: "
сейчас юзаю вот такую конструкцию —
if (NULL!=(headptr=strstr(memptr,"Content-Length: ")) || NULL!=(headptr=strstr(memptr,"Content-length: "))) { headptr += 16;

хотелось бы if (NULL!=(headptr=strstrCustom(memptr,"content-length: "))...

Быстрые алгоритмы типа Бойера-Мура тоже юзаю, но в данном случае это, как бы сказать, overhead...
Вот StrStrI из WinApi подходит, но нужен shlwapi.dll version 4.71 or later

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

И еще к тому, что я сказал, если подумаешь то обратишь внимание на то, что strstr функция сишная и ничего там от ++ ничего нет,
а просили аналог, поэтому предлагать решения из boost который является дополнительной libой из c++ глупо.

Напоминаю ответ, на который я возражаю

D>>переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией.

Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.

D>И еще к тому, что я сказал, если подумаешь то обратишь внимание на то, что strstr функция сишная и ничего там от ++ ничего нет,
D>а просили аналог, поэтому предлагать решения из boost который является дополнительной libой из c++ глупо.
не в языке дело. У вас тут ( http://rsdn.ru/forum/cpp/3568736.1.aspx

Автор: dynamic
Дата: 14.10.09

) — метод прямого перебора (, его сложность — O(n*m) — самая худшая из всех алгоритмов.

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


P>Эта функция мне известна, но беда в том что для ее использования нужно писать цикл.

Да, верно. Не о том я подумал.

P>Вот StrStrI из WinApi подходит, но нужен shlwapi.dll version 4.71 or later

И что ? Думаешь, его может не быть ?

Minimum operating systems Windows 2000, Windows NT 4.0 with Internet Explorer 4.0, Windows 98, Windows 95 with Internet Explorer 4.0

Если уж под W95 могла работать, то...

Вдогонку. Там, похоже, в shlwapi вообще минимум — это 4.71. Для всего Str* семейства это так.