Inplace string replacement in C

Question

Write a function

void inplace(char *str, 
             const char pattern, 
             const char* replacement, 
             size_t mlen)

Input:
str: a string ending with \0. the input indicates that we need an inplace algorithm.

pattern: a letter.

replacement: a string.

mlen: the size of the memory holds the string str starts from the beginning of the memory and that mlen should be larger than strlen(str)

---

The final result is still pointed by str.

Note that all occurrence of pattern should be replaced.

For example,

helelo\0...........

Here "helelo" is the string to replace with '\0' at the end. After '\0' there are still L valid bytes. We want to replace "e" by "123".

A simple approach works like this, we go through str, when a pattern is matched, we shift all the rest with the place to fill the replacement string, then replace the pattern by the replacement.

If the original string is with length n and contains only e, we need (n-1) + (n-2) + ... + 1 shifts.

Is there an algorithm that scans the string with only one pass and constant memory cost?

Answer 1

I think two passes is the minimum. On the first pass, count the number of characters that will be replaced. Given that count and the length of the replacement string, you can compute the length of the final string. (And you should verify that it's going to fit into the buffer.)

On the second pass, you scan the string backwards (starting at the last character), copying characters to their final location. When you encounter the search character, copy the replacement string to that location.

In your example, the increase in length would be 2. So you would

copy str[5] which is '\0' to str[7]
copy str[4] which is 'o' to str[6]
copy str[3] which is 'l' to str[5]
copy str[2] which is 'l' to str[4]
at str[1] you find the 'e' so str[3]='3' str[2]='2' str[1]='1'

At this point the output index is the same as the input index, so you can break the loop.

---

As @chux pointed out in the comments, the cases where the replacement string is either empty, or has exactly one character, can be handled with a single forward pass through the string. So the code should handle those cases separately.

Answer 2

A candidate single pass solution.

For each character in str, recurse. After the recursion, do the replacement.

It does recurse heavily.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

// return 0:success else 1:fail
static int inplace_help(char *dest, const char *src, int pattern,
        const char* replacement, size_t rlen, size_t mlen) {
  printf("'%p' '%s' %c\n", dest, src, pattern);
  if (*src == pattern) {
    if (rlen > mlen) return 1;
    if (inplace_help(dest + rlen, src + 1, pattern, replacement, rlen,
            mlen - rlen)) return 1;
    memcpy(dest, replacement, rlen);
    return 0;
  }
  if (mlen == 0) return 1;
  int replace1 = *src;
  if (*src) {
    if (inplace_help(dest + 1, src + 1, pattern, replacement, rlen, mlen - 1)) {
      return 1;
    }
  }
  *dest = replace1;
  return 0;
}

void inplace(char *str, const char pattern, const char* replacement,
        size_t mlen) {
  if (pattern == 0) return;
  if (mlen == 0) return;
  if (*replacement == 0) return;  // Insure str does not shrink.
  inplace_help(str, str, pattern, replacement, strlen(replacement), mlen - 1);
}

int main(void) {
  char str[1000] = "eeeeec";
  inplace(str, 'e', "1234", sizeof str);
  printf("'%s'\n", str);  // --> '12341234123412341234c'
  return 0;
}

Answer 3

The following assumes that the memory allocated to the string has been initialized to something at some point in time, since standard C does not seem to allow access to uninitialized memory. In practice, it will work fine.

It does precisely two scans: the first one is over the entire allocated space, and moves the string to the right-hand edge of the space. The second scan is over the string itself, which it moves back to the left-hand edge while it does replacements.

I changed the prototype to return 0 on success; -1 on failure. I also allow the pattern to be a string. (Maybe a single character was intentional? Easy to change, anyway.) (As written, pattern must not be length zero. Should be checked.)

int inplace(char *str, 
            const char* pattern, 
            const char* replacement, 
            size_t mlen) {
  /* We don't know how long the string is, but we know that it ends
     with a NUL byte, so every time we hit a NUL byte, we reset
     the output pointer.
   */
  char* left = str + mlen;
  char* right = left;
  while (left > str) {
    if (!*--left) right = str + mlen;
    *--right = *left;
  }

  /* Naive left-to-right scan. KMP or BM would be more efficient. */

  size_t patlen = strlen(pattern);
  size_t replen = strlen(replacement);
  for (;;) {
    if (0 == strncmp(pattern, right, patlen)) {
      right += patlen;
      if (right - left < replen) return -1;
      memcpy(left, replacement, replen);
      left += replen;
    } else {
      if (!(*left++ = *right++)) break;
    }
  }
  return 0;
}