Как я могу найти подстроку в буфере, который содержит ноль? - PullRequest
Новая
       13

Как я могу найти подстроку в буфере, который содержит ноль?

4 голосов
/ 15 марта 2011

Используя C, мне нужно найти подстроку в буфере, который может содержать нули. 

haystack = "Some text\0\0\0\0 that has embedded nulls".
needle   = "has embedded"r

Мне нужно вернуть начало подстроки или нуль similat в strstr (): 

request_segment_end = mystrstr(request_segment_start, boundary);

Существуют ли какие-либо существующие реализации, о которых вы знаете?

Обновление

Я нашел реализации memove в поиске кода Google, которые я скопировал.здесь дословно, не проверено, 

 /*
 * memmem.c
 *
 * Find a byte string inside a longer byte string
 *
 * This uses the "Not So Naive" algorithm, a very simple but
 * usually effective algorithm, see:
 *
 * http://www-igm.univ-mlv.fr/~lecroq/string/
 */

#include <string.h>

void *memmem(const void *haystack, size_t n, const void *needle, size_t m)
{
        const unsigned char *y = (const unsigned char *)haystack;
        const unsigned char *x = (const unsigned char *)needle;

        size_t j, k, l;

        if (m > n || !m || !n)
                return NULL;

        if (1 != m) {
                if (x[0] == x[1]) {
                        k = 2;
                        l = 1;
                } else {
                        k = 1;
                        l = 2;
                }

                j = 0;
                while (j <= n - m) {
                        if (x[1] != y[j + 1]) {
                                j += k;
                        } else {
                                if (!memcmp(x + 2, y + j + 2, m - 2)
                                    && x[0] == y[j])
                                        return (void *)&y[j];
                                j += l;
                        }
                }
        } else
                do {
                        if (*y == *x)
                                return (void *)y;
                        y++;
                } while (--n);

        return NULL;
}

Ответы [ 2 ]

8 голосов
/ 15 марта 2011

Вы можете использовать memmem, если вы находитесь в системе, в которой он есть, например, в linux (это расширение GNU). Точно так же, как strstr, но работает с байтами и требует длины обеих «строк», так как он не проверяет строки, заканчивающиеся нулем. 

#include <string.h>

void *memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen);
4 голосов
/ 15 марта 2011

Мне не имеет смысла, чтобы "строка" содержала нулевые символы. Строки заканчиваются нулем, поэтому первое вхождение отмечает конец строки. Кроме того, что сказать, что нулевой терминатор после слова "nulls" не имеет больше символов после него.

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

char *search_buffer(char *haystack, size_t haystacklen, char *needle, size_t needlelen)
{   /* warning: O(n^2) */
    int searchlen = haystacklen - needlelen + 1;
    for ( ; searchlen-- > 0; haystack++)
        if (!memcmp(haystack, needle, needlelen))
            return haystack;
    return NULL;
}

char haystack[] = "Some text\0\0\0\0 that has embedded nulls";
size_t haylen = sizeof(haystack)-1; /* exclude null terminator from length */
char needle[] = "has embedded";
size_t needlen = sizeof(needle)-1; /* exclude null terminator from length */
char *res = search_buffer(haystack, haylen, needle, needlen);
...