strstr() for a string that is NOT null-terminated

Question

How do I do the in-place equivalent of strstr() for a counted string (i.e. not null-terminated) in C?

Answer 1

See if the function below works for you. I haven't tested it thoroughly, so I would suggest you do so.

char *sstrstr(char *haystack, char *needle, size_t length) {     size_t needle_length = strlen(needle);     size_t i;     for (i = 0; i < length; i++) {         if (i + needle_length > length) {             return NULL;         }         if (strncmp(&haystack[i], needle, needle_length) == 0) {             return &haystack[i];         }     }     return NULL; } 

Answer 2

If you're afraid of O(m*n) behaviour - basically, you needn't, such cases don't occur naturally - here's a KMP implementation I had lying around which I've modified to take the length of the haystack. Also a wrapper. If you want to do repeated searches, write your own and reuse the borders array.

No guarantees for bug-freeness, but it seems to still work.

int *kmp_borders(char *needle, size_t nlen){     if (!needle) return NULL;     int i, j, *borders = malloc((nlen+1)*sizeof(*borders));     if (!borders) return NULL;     i = 0;     j = -1;     borders[i] = j;     while((size_t)i < nlen){         while(j >= 0 && needle[i] != needle[j]){             j = borders[j];         }         ++i;         ++j;         borders[i] = j;     }     return borders; }  char *kmp_search(char *haystack, size_t haylen, char *needle, size_t nlen, int *borders){     size_t max_index = haylen-nlen, i = 0, j = 0;     while(i <= max_index){         while(j < nlen && *haystack && needle[j] == *haystack){             ++j;             ++haystack;         }         if (j == nlen){             return haystack-nlen;         }         if (!(*haystack)){             return NULL;         }         if (j == 0){             ++haystack;             ++i;         } else {             do{                 i += j - (size_t)borders[j];                 j = borders[j];             }while(j > 0 && needle[j] != *haystack);         }     }     return NULL; }  char *sstrnstr(char *haystack, char *needle, size_t haylen){     if (!haystack || !needle){         return NULL;     }     size_t nlen = strlen(needle);     if (haylen < nlen){         return NULL;     }     int *borders = kmp_borders(needle, nlen);     if (!borders){         return NULL;     }     char *match = kmp_search(haystack, haylen, needle, nlen, borders);     free(borders);     return match; }