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 有効なバイトがある後。「e」を「123」に置き換えます。

単純なアプローチは次のように機能strします。パターンが一致すると、残りのすべてを置換文字列を埋める場所にシフトし、パターンを置換で置き換えます。

元の文字列に長さnがあり、 のみが含まれている場合は、シフトがe必要です。(n-1) + (n-2) + ... + 1

文字列を 1 回のパスと一定のメモリ コストでスキャンするアルゴリズムはありますか?

4

3 に答える 3

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 に答える