文字列置換の妄想、

ふと文字列置換の処理は重い処理じゃないかな、と思って、簡単に実装しようとした時に、
同じバッファ上のメモリコピーの面倒さに気づいた。
先人ならコレを解決する関数ぐらい作ってるだろう、と "mem"で始まる関数を辞書で探したら、memmoveが出てきた。
なるほど、memmoveはここで使えるんだなって気づいた。
memcpyと違ってmemmoveはコピー先とコピー元のバッファが重なっても正常にコピー(移動だけど)できる事が保障されています。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// dst:対象文字列(十分なバッファを持っていること)  mat:置換対象文字列  rep:置換文字列
int replace(char *dst, const char *mat, const char *rep)
{
	int replace_count = 0;
	int mat_len = strlen(mat);
	int rep_len = strlen(rep);
	while(dst = strstr(dst, mat)){
		memmove(dst+rep_len, dst+mat_len, strlen(dst+mat_len)+1);
		memcpy(dst, rep, rep_len);
		dst += rep_len;
		replace_count++;
	}
	return replace_count;
}


main(){
	char str[1000] = "abcabcabcabcabc";
	printf("%s\n", str);
	int rep = replace(str, "abc", "1");
	printf("%s(%d)\n", str, rep);
	return;
}

"abc"を"1"に置換えて、置換えた回数を返すreplace関数を作ってみました。
ここまでだと、memmove使えてよかったねーって話なんですが、これで終わりってわけでもなく。

重大な欠点として"バッファが十分にあること"を前提とした設計だということ。
置換えの対象になる文字列より置換える文字列のほうが長ければ、バッファオーバーフローが発生してしまいます。
その辺は可変長の文字列ライブラリや、大人しくC++でstring使えよってことで。

また、この実装では、何度も同じ箇所を移動させる事が出てきます。
置換えは置換える文字列を入れるための文字列の移動がほとんどなので、
コレをどうにかすればもっと早くなるんじゃないかなーって思うんですが、
ちょっと良い方法が思いつかないです。
最初に置換える場所のオフセットを配列にいれる方法を考えたりしてみましたが、これはそれほど大きくないけど一時領域が必要になりますし、置換え後のオフセットのズレも計算しないといけないので、ちょっとめんどいですよね。
うーん。