就地字符串替换用C

Question

写一个函数

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

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

pattern：一封信。

replacement：一个字符串。

mlen：内存的大小，从内存的开头包含字符串str开始，且mlen应大于strlen(str)

---

最终的结果仍然由str指出。

请注意，应该更换所有出现的花样。

例如，

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

这里 “helelo” 是在端部与'\0'替换的字符串。在'\0'之后仍然有L个有效字节。我们想用“123”代替“e”。

一个简单的方法是这样的，我们通过str，当一个模式匹配时，我们将所有剩下的部分替换为填充替换字符串的地方，然后用替换替换模式。

如果原始字符串，长度n只包含e，我们需要(n-1) + (n-2) + ... + 1变化。

有没有一种算法只扫描字符串只有一个通过和恒定的内存成本？

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在评论中指出，其中该替换字符串或者为空，或者恰好具有一个字符的情况下，可以用单个处理前进穿过该字符串。所以代码应该分别处理这些情况。

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似乎没有允许访问未初始化的内存。在实践中，它会正常工作。

这正是做两次扫描：第一个是在整个分配的空间，并移动字符串到空间的右手边。第二次扫描是在字符串本身上进行的，它会在替换时移回到左侧边缘。

我改变了原型成功返回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; 
}