Здраствуйте, хотел выяснить по поводу возможных вариантов организации поиска подстроки в большом файле. Как правило, из файла читают по n байт, а функциям поиска и pcre надо строку полностью скармливать, а не по частям, в этом порблема. Подскажите какие есть реализации и варианты алгоритма.

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

А>Здраствуйте, хотел выяснить по поводу возможных вариантов организации поиска подстроки в большом файле. Как правило, из файла читают по n байт, а функциям поиска и pcre надо строку полностью скармливать, а не по частям, в этом порблема. Подскажите какие есть реализации и варианты алгоритма.
Алгоритмы Бойера-Мура или Кнута-Морриса-Пратта. Для любого из них достаточно функции "дай мне очередной символ".

Кнута-Морриса-Пратта у меня не собрался к сожалению. А реализации этой функции типа дай мне следующий символ есть? ну или идеи как это сделать? вобще было бы круто такую функцию для пцре...

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

А>Кнута-Морриса-Пратта у меня не собрался к сожалению. А реализации этой функции типа дай мне следующий символ есть? ну или идеи как это сделать? вобще было бы круто такую функцию для пцре...
А какие сложности?
Мы читаем из файла по N байт в буфер. Храним позицию символа, который надо отдать, относительно начала буфера. Если буфер не кончился, отдаем очередной символ, иначе читаем из файла очередную порцию и обнуляем позицию.

char buf[N];
int bufPos;
...
char getNextChar()
{
    if( bufPos >= N )
    {
        fillBuffer();
        bufPos = 0;
    }
    return buf[bufPos++];
}

А к pcre ее по-простому не приделать, потому что для регэкспов требуются возвраты к ранее просмотренным частям строки.

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

C>А к pcre ее по-простому не приделать, потому что для регэкспов требуются возвраты к ранее просмотренным частям строки.
Можно использовать из Boost.Spirit реализацию multi_pass итератора — он запоминает некоторое количество пройденых символов.

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

Читай про memory mapped files.

короче по данному сабжу, регэкспы прикручиваются для этих целей, но хз как это правильно юзать.
http://www.rsdn.ru/forum/message/2682287.1.aspx

Автор: Андрeй
Дата: 05.10.07

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

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

C>>А к pcre ее по-простому не приделать, потому что для регэкспов требуются возвраты к ранее просмотренным частям строки.
C>Можно использовать из Boost.Spirit реализацию multi_pass итератора — он запоминает некоторое количество пройденых символов.

регэкспы прикручиваются для этих целей, но хз как это правильно юзать.
http://www.rsdn.ru/forum/message/2682287.1.aspx

Автор: Андрeй
Дата: 05.10.07

Подскажите а через Boost какую функцию юзать?