c - C中的就地字符串替换

Question

写一个函数

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

输入:
str:以\0结尾的字符串。输入表明我们需要一个就地算法。

pattern:一个字母。

替换:字符串。

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

---

最终结果还是由str指向。

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

例如，

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

这里的“helelo”是要在末尾用'\0' 替换的字符串。 '\0' 之后还有 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 '\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'

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

---

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