Function which removes a given word from a string

Question

Any improvements? Please review.

It could be faster if I use own strstr function which searches from the end (less memory to move) but I wanted to use only the standard functions.

char *removestr(char *str, const char *word)
{
    char *ptr = str;
    size_t len = strlen(word);
    while((ptr = strstr(ptr, word)))
    {
        if(isalnum(*(ptr + len)) || (str != ptr && isalnum(*(ptr -1))))
        {
            ptr += len;
        }
        else
        {
            memmove(ptr, ptr + len, strlen(ptr + len) + 1);
        }
    }
    return str;
}

Answer 1

I would suggest renaming your variables. str, ptr, and len don't tell us much about what they're meant to be.

size_t len = strlen(word);

Since this is never going to change (because it's abstractly a property of a const input) you might as well mark it const.

while((ptr = strstr(ptr, word)))

I would put a comment here, not least as a note that the assignment is deliberate. (Because so often a single equals sign in an if or while implies a bug). Really you could do with a few more comments throughout to say why you're doing things: For example the if(isalnum... could be commented to explain that you only want to remove whole words.

strlen(ptr + len)

This may work fine, but it's a moderately expensive thing to do because it has to run down the length of the remaining list. I would be inclined to measure the length str at the start outside the loop, and track it across updates.

memmove(ptr, ptr + len, strlen(ptr + len) + 1);

Again this works fine, but it has to copy (quite slowly and carefully) the whole remaining string. Because it's in a loop, this becomes an \$ O(n^2) \$ function. One solution would be to only move back the string up to the next time word appears. This would mean a bit more complexity tracking the size of the gap that you're building up, but it would reduce the overall complexity of the function to \$ O(n) \$.

Answer 2

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 >