C中的就地字符串替换

Question

写一个函数

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

输入：
str：以[=12=]结尾的字符串。输入表明我们需要一个就地算法。

pattern：一封信。

replacement：一个字符串。

mlen：内存中存放字符串的大小str从内存的开头开始，mlen应该大于strlen(str)

最后的结果还是str指向的。

请注意，应替换所有出现的模式。

例如，

helelo[=20=]...........

这里的"helelo"就是最后要用'[=21=]'替换的字符串。在'[=21=]'之后还有L个有效字节。我们想用“123”替换"e"。

一个简单的方法是这样的，我们通过str，当匹配到一个模式时，我们将所有剩余的地方移动到填充替换字符串的位置，然后用替换替换模式。

如果原始字符串的长度为 n 且仅包含 e，我们需要 (n-1) + (n-2) + ... + 1 次移位。

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

Answer 1

我认为至少要通过两次。在第一遍中，计算将被替换的字符数。鉴于 count 和替换字符串的长度，您可以计算最终字符串的长度。（并且您应该验证它是否适合缓冲区。）

在第二遍中，您向后扫描字符串（从最后一个字符开始），将字符复制到它们的最终位置。当您遇到搜索字符时，将替换字符串复制到该位置。

在你的例子中，长度增加了 2。所以你会

copy str[5] which is '[=10=]' 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'

此时输出索引与输入索引相同，因此可以打破循环。

正如@chux 在评论中指出的那样，替换字符串为空或只有一个字符的情况，可以通过对字符串进行一次正向传递来处理。所以代码应该分别处理这些情况。

Answer 2

候选单遍解决方案。

对于str中的每个字符，递归。递归后，做替换。

它确实大量递归。

#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

以下假设分配给字符串的内存在某个时间点已被初始化为某些东西，因为标准 C 似乎不允许访问未初始化的内存。在实践中，它会很好地工作。

它恰好进行了两次扫描：第一次扫描整个分配的 space，并将字符串移动到 space 的右手边缘。第二次扫描是在字符串本身上进行的，它在进行替换时将其移回左侧边缘。

我成功地将原型更改为 return 0； -1 失败。我也允许模式是一个字符串。（也许一个字符是故意的？无论如何很容易改变。）（如所写，模式长度不能为零。应该检查。）

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;
}

C中的就地字符串替换

Inplace string replacement in C

c

algorithm

string-algorithm