C: поиск строки в файле

Question

Если у меня есть:

const char *mystr = "cheesecakes"; 
FILE *myfile = fopen("path/to/file.exe","r"); 

Мне нужно написать функцию, чтобы определить, содержит ли myfile вхождений mystr. Может ли кто-нибудь мне помочь? Благодаря!

UPDATE: Итак, на платформе, которую мне нужно развернуть, нет memstr. Кто-нибудь знает о свободной реализации, которую я могу использовать в своем коде?

Answer 1

Если вы не может соответствовать весь файл в память, и у вас есть доступ к расширению GNU memmem(), то:

• читать столько, сколько вы можете в буфер;
• Поиск буфера с memmem(buffer, len, mystr, strlen(mystr) + 1);
• Отбросить всех, кроме последних strlen(mystr) символов буфера, и перенести их в начало;
• Повторяйте до конца файла.

Если вы не имеете memmem, то вы можете реализовать его в виде простого С помощью memchr и memcmp, например, так:

/* 
* The memmem() function finds the start of the first occurrence of the 
* substring 'needle' of length 'nlen' in the memory area 'haystack' of 
* length 'hlen'. 
* 
* The return value is a pointer to the beginning of the sub-string, or 
* NULL if the substring is not found. 
*/ 
void *memmem(const void *haystack, size_t hlen, const void *needle, size_t nlen) 
{ 
    int needle_first; 
    const void *p = haystack; 
    size_t plen = hlen; 

    if (!nlen) 
     return NULL; 

    needle_first = *(unsigned char *)needle; 

    while (plen >= nlen && (p = memchr(p, needle_first, plen - nlen + 1))) 
    { 
     if (!memcmp(p, needle, nlen)) 
      return (void *)p; 

     p++; 
     plen = hlen - (p - haystack); 
    } 

    return NULL; 
} 

Answer 2

Поскольку нет memmem или memstr найти строку в двоичный массив (другие предложили прочитать его в памяти и использовать strstr - нет, это не сработает), вы должны прочитать его byte by byte с помощью «fgetch» ​​и написать небольшой конечный автомат, чтобы он соответствовал ему при чтении.

Answer 3

chat match = "findthis"; 
int depth = 0; 
while(not eof) 
{ 
    char ch = getonebyte(); 
    if(ch == match[depth]) 
    { 
     if (depth == strlen(match)) 
      break; 
     else 
      depth++; 
     } 
     else 
      depth = 0; 
} 

примерно (я уверен, что выключены единицами есть)

Answer 4

Вот хлопнул вместе версию. Он не имеет проверки ошибок и, вероятно, имеет ошибки переполнения. Но я думаю, что он находит нужную строку и учитывает обратный отсчет, необходимый для парных подстрок. Я сомневаюсь, что осталось более 15 ошибок.

Редактировать: В первом ответе было по крайней мере одно. Я проснулся посреди ночи и понял, что проверка назад была неправильной. Он не нашел «12123» в «1212123». Это может быть и не так, но, по крайней мере, сейчас это находит.

int main(int argc, char* argv[]) 
{ 
    FILE *fp; 
    char *find, *hist; 
    int len, pos=0, hl=0, i; 
    char c; 

    fp = fopen(argv[1], "r"); 
    find = argv[2]; 
    len = (int)strlen(find); 
    hist = malloc(len); 
    memset(hist, 0, len); 
    while (!feof(fp)) { 
     c = fgetc(fp); 
     if (find[pos++] == c) { 
      if (pos == len) { 
       printf("Found it\n"); 
       return 1; 
      } 
     } 
     else { 
      // check history buffer (kludge for backtracking) 
      if (pos > 0) { 
       pos = 0; 
       for (i = 0; i < len - 1; i++) 
        if (0 == memcmp(hist+len-i-1, find, i + 1)) { 
        // we had a mismatch, but the history matches up to len i 
        pos = i; 
       } 
      } 
     } 
     // update history buffer - this is innefficient - better as circular buffer 
     memmove(hist, hist + 1, len - 1); 
     hist[len-1] = c; 
    } 
    printf("Not found\n"); 
} 

Answer 5

Смотрите здесь:

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

для реализации Бойер-Мура в C99. Это очень распространенный алгоритм поиска строк и работает в O (n).

Answer 6

Вот функция, которая будет искать строку в буфере.

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

/***************************************************** 
const char *buffer pointer to your read buffer (the larger, the better). 
size_t bufsize  the size of your buffer 
const char *pattern pattern you are looking for. 

Returns an index into the buffer if pattern is found. 
-1 if pattern is not found. 

Sample: 
    pos = findPattern (buffer, BUF_SIZE, "cheesecakes"); 
*****************************************************/ 

int findPattern (const char *buffer, size_t bufSize, const char *pattern) 
{ 
    int i,j; 
    int patternLen; 

    // minor optimization. Determine patternLen so we don't 
    // bother searching buffer if fewer than patternLen bytes remain. 
    patternLen = strlen (pattern); 

    for (i=0; i<bufSize-patternLen; ++i) 
    { 
     for (j=0; j<patternLen; ++j) 
     { 
      if (buffer[i+j] != pattern[j]) 
      { 
       break; 
      } 
     } 
     if (j == patternLen) 
     { 
      return i; 
     } 
    } 
    return -1; 
}