problems with strstr

[izabera]

it must not compute strlen(haystack)

char haystack[] = { 'A', 'A', ...... 10GB ...... 'A', 0 },
     needle[]   = { 'A', 0 };
char *ptr = strstr(haystack, needle); // takes ages

and allocating a buffer as large as (or in this case, 8 times larger than) the needle withalloca is an amazingly bad idea

[maandree]

I will take a look a this later. Do you have any suggestion on how to avoid alloca? I cannot use malloc because it [malloc] can fail whilst strstr cannot.

[izabera]

glibc and musl use the two way algorithm described here: http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 it requires O(1) space