1

写一个函数

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移位。

是否有一种算法可以仅通过一次扫描和恒定的内存成本来扫描字符串？

4

3 回答 3

4

我认为两次通过是最低限度的。在第一次通过时，计算将被替换的字符数。鉴于此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 在评论中指出的那样，替换字符串为空或只有一个字符的情况可以通过字符串进行一次前向传递来处理。所以代码应该分别处理这些情况。

于 2015-09-01T01:11:54.787 回答
1

候选单通解决方案。

对于 中的每个字符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;
}
于 2015-09-01T02:57:26.697 回答
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;
}
于 2015-09-01T05:47:33.527 回答