在C中替换字符串
写一个函数
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
移位。
是否有一种算法只用一次通过和恒定的内存成本扫描字符串?
我认为两次通过是最小的。 在第一遍中,计算要替换的字符数。 给定count
和替换字符串的长度,您可以计算最终字符串的长度。 (你应该validation它是否适合缓冲区。)
在第二遍中,您向后扫描字符串(从最后一个字符开始),将字符复制到其最终位置。 遇到搜索字符时,将替换字符串复制到该位置。
在你的例子中,长度的增加将是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在注释中指出的那样,替换字符串为空或者只有一个字符的情况可以通过字符串中的单个正向传递来处理。 所以代码应该分别处理这些情况。
候选单程解决方案。
对于str
每个字符,递归。 递归后,进行替换。
它确实很重要。
#include #include #include #include // 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; }
以下假设分配给字符串的内存已在某个时间点初始化为某些内容,因为标准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; }