(referring to an allocation-free strstr if strings had an associated length)

If a string was a (pointer,length) pair, then strstr would return a pair (pointer+offset,length-offset) where, just like in the original strstr, the new pointer points into the existing string. No allocation needed

(But what about the pointer-length pair that has to be created? Well, it will live on the stack just like the return value from the original strstr, which has to be stored somewhere also.)

I don't need to explain how I'd implement it because every obvious implementation of the strstr algorithm doesn't need to allocate because it's a substring search! Search operations are pure and don't mutate!

Every single implementation of strstr or equivalent in every single programming language I have ever seen does not require an allocation. It either returns a pointer to the location of the first matched result, or returns the character index of the first match. That's it.

Any other absurd implementation you can think up to justify null-terminated strings - like returning a copy of the string with a null terminator after the match - just doesn't make any sense. That's a different operation.

  strstr - locate a substring

  int strstr(string haystack, string needle, int offset);

  The strstr() function finds the first occurrence of the substring needle
  in the string haystack, starting from position offset in haystack.

  This function returns the index of the first character in haystack after
  offset where needle can be found, or -1 if the substring is not found (or
  if offset is out of bounds for haystack).

(I don't have a problem with NUL-terminated strings, but couldn't resist a little sideways thinking on how an alternate library implementation for strings might work.)