Поиск текста в двоичных данных

Question

У меня есть двоичные данные, которые содержат текст. Текст известен. Что может быть быстрым методом для поиска этого текста:

Как например.

This is text 1---
!@##$%%#^%&!%^$! 

Как мне найти текст This is text 2.

В настоящее время я делаю как:

size_t count = 0;
size_t s_len = strlen("This is text 2");

//Assume data_len is length of the data from which text is to be found and data is pointer (char*) to the start of it.
for(; count < data_len; ++count)
{
    if(!memcmp("This is text 2", data + count, s_len)
    {
         printf("%s\n", "Hurray found you...");
    }
}

• Есть ли другой способ, более эффективный способ сделать это
• Будет ли замена ++count logic на memchr('T') logic help <= Пожалуйста, игнорируйте, если это утверждение не ясно </li>
• Какой должна быть средняя сложность big-O в случае memchr

Answer 1

В стандартном C нет ничего, что могло бы вам помочь, но есть расширение GNU memmem(), которое делает это:

#define TEXT2 "This is text 2"

char *pos = memmem(data, data_len, TEXT2, sizeof(TEXT2));

if (pos != NULL)
    /* Found it. */

Если вам нужно быть переносимым на системы, которые нене имея этого, вы можете взять glibc реализацию memmem() и включить ее в свою программу.

Answer 2

Существуют алгоритмы для выполнения именно этого с большей сложностью, чем повторяющиеся memcmp (что реализовано очевидным способом и имеет очевидную сложность для близких совпадений).

Известные алгоритмы Бойер-Мур и Кнут-Моррис-Пратт .Это только два примера.Общая категория, в которую попадают эти слова, - «соответствие строк».

Answer 3

Я знаю, что вопрос касается языка программирования C, но вы пытались использовать strings unix tool: http://en.wikipedia.org/wiki/Strings_(Unix) с grep ?

$ strings datafile | grep "your text"

РЕДАКТИРОВАТЬ:

Если вы хотите использовать C, я предлагаю сделать эту простую оптимизацию:

size_t count = 0;
size_t s_len = strlen("This is text 2");

for(; count < data_len; ++count)
{
    if (!isprint(data[count])) continue;

    if(!memcmp("This is text 2", data + count, s_len)
    {
     printf("%s\n", "Hurray found you...");
    }
}

Если вы хотите повысить производительность, я предлагаю вам искать и использоватьалгоритм сопоставления строк.