Order of complexity higher than needed
With memmove()
, which execution time varies linearly with strlen(str)
, inside a loop which iteration count can depend on strlen(str)
, this algorithm is at least \$ O(n^2) \$ and a \$ O(n) \$ is possible. Use separate pointers to read from str
and write to str
can accomplish \$ O(n) \$ - still in the forward direction. See below.
What if arguments overlap?
word
could exist at the end of str
, and so removestr(char *str, const char *word)
must account that word[]
may change anytime str[]
changes. To inform the compiler this situation is not relevant employ restrict
.
// char *removestr(char *str, const char *word)
char *removestr(char *restrict str, const char *restrict word)
This may improve performance a bit as it can allow various compiler optimizations
Avoid UB
is...(x)
functions are UB when x < 0 && x != EOF
as they are designed for unsigned char
and EOF
. As a char
may be negative, cast to (unsigned char)
to cope with this pesky C nuance.
// isalnum(*(ptr + len)
isalnum((unsigned char) *(ptr + len))
Sample lightly tested \$ O(n) \$ code following OP's lead of while((ptr = strstr(ptr, word)))
(Really \$ O(strlen(str) * strlen(word)\$ vs. OP's \$ O(strlen(str)^2 * strlen(word)\$).
// Remove all "stand-alone" occurrences of `word` from `str`.
// For `word` to stand-alone", it must not be preceded nor followed by letter/digit
char *removestr(char * restrict str, const char *restrict word) {
size_t w_len = strlen(word);
if (w_len == 0) {
return str;
}
const char *src = str;
char *dest = str;
char *token;
while ((token = strstr(src, word)) != NULL) {
// Copy sub-string
while (src < token) { // Could alternatively use memmove() here
*dest++ = *src++;
}
if (isalnum((unsigned char) src[w_len]) ||
(src > str && isalnum((unsigned char) src[-1]))) {
// `word` match is not "stand-alone"
*dest++ = *src++;
} else {
// skip `word`
src += w_len;
}
}
// copy rest of `str`
while ((*dest++ = *src++) != '\0');
return str;
}
Tests
void removestr_test(const char *str, const char *word) {
char *test_str = strdup(str);
char *result = removestr(test_str, word);
printf("%d <%s> <%s> --> <%s>\n", result == test_str, str, word, test_str);
}
int main(void) {
removestr_test("", "the");
removestr_test("the", "the");
removestr_test("the beginning", "the");
removestr_test("in the beginning", "the");
removestr_test("end the", "the");
removestr_test("thenot thenot notthe notthe", "the");
removestr_test("xx the xx the xx the xx the xx the xx the", "the");
return 0;
}
Output
1 <> <the> --> <>
1 <the> <the> --> <>
1 <the beginning> <the> --> < beginning>
1 <in the beginning> <the> --> <in beginning>
1 <end the> <the> --> <end >
1 <thenot thenot notthe notthe> <the> --> <thenot thenot notthe notthe>
1 <xx the xx the xx the xx the xx the xx the> <the> --> <xx xx xx xx xx xx >