就地字符串替换用C [英] Inplace string replacement in C

问题描述

写一个函数

 无效就地（的char * str中，
             为const char格局，
             为const char *更换，
             为size_t MLEN）
 

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

模式：一个字母。

替换：字符串。

MLEN ：内存的大小，持有 STR 从内存以及年初开始字符串 MLEN 应大于的strlen（STR）

---

最后的结果仍然是由 STR 指出。

请注意该模式的所有发生应及时更换。

例如，

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

下面helelo是末，以取代'\\ 0'的字符串。后'\\ 0'还有L适用字节。我们要替换E的123。

有一个简单的方法是这样的，我们通过 STR ，当一个模式匹配，我们转移所有的休息与填充替换字符串的地方，然后替换由替换模式

如果原来的字符串，长度 N ，并且只包含电子，我们需要 （N-1）+（N-2）+ ... + 1 的变化。

  

有没有办法，只有一个通行证和常量存储器成本扫描线算法？

解决方案

我觉得两次传球是最低的。在第一次，计数将被替换的字符数。鉴于计数和替换字符串的长度，就可以计算出最终的字符串的长度。 （你应该确认它要装入缓冲区。）

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

在你的榜样，在长度上增加为2。所以，你会

 复制海峡[5]这是'\\ 0'为str [7]
副本海峡[4]这是O为str [6]
副本STR [3]这是'L'为str [5]
拷贝海峡[2]这是'L'为str [4]
在海峡[1]你找到的'e'这样STR [3] ='3'海峡[2] ='2'海峡[1] ='1'
 

此时产出指数是一样的投入指数，这样你就可以打破循环。

---

正如@chux评价指出，其中该替换字符串可以是空的，或者有一个字符的情况下，可以用一个正向处理通过串。因此，code应单独处理这些情况。

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?

解决方案

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.

这篇关于就地字符串替换用C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！