Самый быстрый способ выполнить поиск подстроки без учета регистра в C / C++?

Почему вы используете _strlwr (строка); в init_stristr ()? Это не стандартная функция. Предположительно это для поддержки локали, но, поскольку это нестандартно, я бы просто использовал:

char_table[i] = tolower(i);

Я бы посоветовал вам воспользоваться некоторыми из уже существующих распространенных реализаций strcasestr. Например, glib, glibc, OpenBSD, FreeBSD и т. д. Вы можете найти больше с помощью google.com/codesearch. Затем вы можете измерить производительность и сравнить разные реализации.

Опубликованный вами код примерно вдвое медленнее, чем strcasestr.

$ gcc -Wall -o my_stristr my_stristr.c
steve@solaris:~/code/tmp
$ gcc -Wall -o strcasestr strcasestr.c 
steve@solaris:~/code/tmp
$ ./bench ./my_stristr > my_stristr.result ; ./bench ./strcasestr > strcasestr.result;
steve@solaris:~/code/tmp
$ cat my_stristr.result 
run 1... time = 6.32
run 2... time = 6.31
run 3... time = 6.31
run 4... time = 6.31
run 5... time = 6.32
run 6... time = 6.31
run 7... time = 6.31
run 8... time = 6.31
run 9... time = 6.31
run 10... time = 6.31
average user time over 10 runs = 6.3120
steve@solaris:~/code/tmp
$ cat strcasestr.result 
run 1... time = 3.82
run 2... time = 3.82
run 3... time = 3.82
run 4... time = 3.82
run 5... time = 3.82
run 6... time = 3.82
run 7... time = 3.82
run 8... time = 3.82
run 9... time = 3.82
run 10... time = 3.82
average user time over 10 runs = 3.8200
steve@solaris:~/code/tmp

Функция main была:

int main(void)
{
        char * needle = "hello";
        char haystack[1024];
        int i;

        for(i=0;i<sizeof(haystack)-strlen(needle)-1;++i)
        {
                haystack[i]='A'+i%57;
        }
        memcpy(haystack+i,needle, strlen(needle)+1);
        /*printf("%s\n%d\n", haystack, haystack[strlen(haystack)]);*/
        init_stristr();

        for (i=0;i<1000000;++i)
        {
                /*my_stristr(haystack, needle);*/
                strcasestr(haystack,needle);
        }


        return 0;
}

Он был соответствующим образом модифицирован для тестирования обеих реализаций. Я замечаю, что, набирая это, я оставил вызов init_stristr, но это не должно сильно изменить ситуацию. bench - это простой сценарий оболочки:

#!/bin/bash
function bc_calc()
{
        echo $(echo "scale=4;$1" | bc)
}
time = "/usr/bin/time -p"
prog = "$1"
accum=0
runs=10
for a in $(jot $runs 1 $runs)
do
        echo -n "run $a... "
        t=$($time $prog 2>&1| grep user | awk '{print $2}')
        echo "time = $t"
        accum=$(bc_calc "$accum+$t")
done

echo -n "average user time over $runs runs = "
echo $(bc_calc "$accum/$runs")

Предполагая, что обе входные строки уже написаны в нижнем регистре.

int StringInStringFindFirst(const char* p_cText, const char* p_cSearchText)
{
    int iTextSize = strlen(p_cText);
    int iSearchTextSize = strlen(p_cSearchText);

    char* p_cFound = NULL;

    if (iTextSize >= iSearchTextSize)
    {
        int iCounter = 0;
        while((iCounter + iSearchTextSize) <= iTextSize)
        {
            if (memcmp( (p_cText + iCounter), p_cSearchText, iSearchTextSize) == 0)
                return  iCounter;
            iCounter ++;
        }
    }

    return -1;
}

Вы также можете попробовать использовать маски ... если, например, большинство строк, которые вы собираетесь сравнивать, содержат только символы от a до z, возможно, стоит сделать что-то вроде этого.

long GetStringMask(const char* p_cText)
{
    long lMask=0;

    while(*p_cText != '\0')
    {       
        if (*p_cText>='a' && *p_cText<='z')
            lMask = lMask | (1 << (*p_cText - 'a') );
        else if (*p_cText != ' ')
        {
            lMask = 0;
            break;      
        }

        p_cText ++;
    }
    return lMask;
}

Затем...

int main(int argc, char* argv[])
{

    char* p_cText = "this is a test";   
    char* p_cSearchText = "test";

    long lTextMask = GetStringMask(p_cText);
    long lSearchMask = GetStringMask(p_cSearchText);

    int iFoundAt = -1;
    // If Both masks are Valid
    if (lTextMask != 0 && lSearchMask != 0)
    {
        if ((lTextMask & lSearchMask) == lSearchMask)
        {       
             iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
        }
    }
    else
    {
        iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
    }


    return 0;
}

Если вы хотите сократить циклы процессора, вы можете подумать об этом - предположим, что мы имеем дело с ASCII, а не с Unicode.

Сделайте статическую таблицу с 256 записями. Каждая запись в таблице составляет 256 бит.

Чтобы проверить, равны ли два символа, вы делаете что-то вроде этого:

if (BitLookup(table[char1], char2)) { /* match */ }

Чтобы построить таблицу, вы устанавливаете бит везде в таблице [char1], где считаете, что это соответствует char2. Таким образом, при построении таблицы вы должны установить биты по индексу для «a» и «A» в «a» -й записи (и «A» -й записи).

Теперь поиск по битам будет медленным (поиск по битам, скорее всего, будет сдвигом, маской и добавлением), поэтому вместо этого вы можете использовать таблицу байтов, чтобы использовать 8 бит для представления 1 бита. Это займет 32К - так что ура - вы нашли компромисс между пространством и временем! Возможно, мы захотим сделать таблицу более гибкой, поэтому предположим, что мы делаем это вместо этого - вместо этого таблица будет определять сравнения.

Два символа считаются совпадающими тогда и только тогда, когда существует функция, определяющая их как эквивалентные. Таким образом, «A» и «a» конгруэнтны для нечувствительности к регистру. «А», «А», «Б» и «В» соответствуют диакритической нечувствительности.

Итак, вы определяете битовые поля, которые соответствуют вашим конгруэнтностям.

#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)

Тогда ваш тест выглядит примерно так:

inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
    return (_congruencyTable[c1][c2] & congruency) != 0;
}

#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)

Такой способ возиться с огромными таблицами - это, кстати, суть ctype.

используйте алгоритм усиления строки. Он доступен, кроссплатформенный, и только файл заголовка (без библиотеки для ссылки). Не говоря уже о том, что вы все равно должны использовать Boost.

#include <boost/algorithm/string/find.hpp>

const char* istrstr( const char* haystack, const char* needle )
{
   using namespace boost;
   iterator_range<char*> result = ifind_first( haystack, needle );
   if ( result ) return result.begin();

   return NULL;
}

Если вы можете управлять строкой иглы так, чтобы она всегда была в нижнем регистре, вы можете написать модифицированную версию stristr (), чтобы избежать поиска для этого и, таким образом, ускорить код. Это не так часто, но может быть быстрее - немного быстрее. Подобные комментарии относятся и к стогу сена, но вы, скорее всего, будете читать стог сена из источников, находящихся вне вашего контроля, поскольку вы не можете быть уверены, что данные соответствуют требованиям.

Стоит ли прибавка в производительности - это вообще вопрос. На 99% приложений ответ «Нет, не стоит». Ваше приложение может быть одним из крошечного меньшинства, когда оно имеет значение. Скорее всего, это не так.

Это не будет учитывать языковой стандарт, но если вы можете изменить IS_ALPHA и TO_UPPER, вы можете заставить его учитывать его.

#define IS_ALPHA(c) (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z'))
#define TO_UPPER(c) ((c) & 0xDF)

char * __cdecl strstri (const char * str1, const char * str2){
        char *cp = (char *) str1;
        char *s1, *s2;

        if ( !*str2 )
            return((char *)str1);

        while (*cp){
                s1 = cp;
                s2 = (char *) str2;

                while ( *s1 && *s2 && (IS_ALPHA(*s1) && IS_ALPHA(*s2))?!(TO_UPPER(*s1) - TO_UPPER(*s2)):!(*s1-*s2))
                        ++s1, ++s2;

                if (!*s2)
                        return(cp);

                ++cp;
        }
        return(NULL);
}

Вы можете использовать функцию StrStrI, которая находит первое вхождение подстроки в строке. При сравнении регистр не учитывается. Не забудьте включить его заголовок - Shlwapi.h. Проверьте это: http://msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx

Для независимого от платформы использования:

const wchar_t *szk_wcsstri(const wchar_t *s1, const wchar_t *s2)
{
    if (s1 == NULL || s2 == NULL) return NULL;
    const wchar_t *cpws1 = s1, *cpws1_, *cpws2;
    char ch1, ch2;
    bool bSame;

    while (*cpws1 != L'\0')
    {
        bSame = true;
        if (*cpws1 != *s2)
        {
            ch1 = towlower(*cpws1);
            ch2 = towlower(*s2);

            if (ch1 == ch2)
                bSame = true;
        }

        if (true == bSame)
        {
            cpws1_ = cpws1;
            cpws2 = s2;
            while (*cpws1_ != L'\0')
            {
                ch1 = towlower(*cpws1_);
                ch2 = towlower(*cpws2);

                if (ch1 != ch2)
                    break;

                cpws2++;

                if (*cpws2 == L'\0')
                    return cpws1_-(cpws2 - s2 - 0x01);
                cpws1_++;
            }
        }
        cpws1++;
    }
    return NULL;
}