字符串替换算法（时间、空间效率）

最有效的替换字符串的函数该怎么写呢？
ReplaceStr(原串，旧串，新串)
要求直接在原字符串上替换，原字符串的空间足够大（即使替换后的字符串变大了，也放得下）

如果新串不比旧串长，原字符串的后续内容逐渐前移
如果新串不比旧串短，原字符串的后续内容逐渐后移
关键是，如何才能使得移动的字节*次数的总数最小？

如果新串不比旧串长，原字符串的后续内容逐渐前移，好像比较简单
如果新串不比旧串短，原字符串的后续内容逐渐后移，好像比较麻烦。。。除非从最后开始匹配旧串。。。。


－－下面这个函数使用了一个char caNewString[MAX_MSG_LENGTH]，感觉不是太好
// 替换字符串中特征字符串为指定字符串
int ReplaceStr(char *sSrc, char *sMatchStr, char *sReplaceStr)
{
        int  StringLen;
        char caNewString[MAX_MSG_LENGTH];

        char *FindPos = strstr(sSrc, sMatchStr);
        if( (!FindPos) || (!sMatchStr) )
                return -1;

        while( FindPos )
        {
                memset(caNewString, 0, sizeof(caNewString));
                StringLen = FindPos - sSrc;
                strncpy(caNewString, sSrc, StringLen);
                strcat(caNewString, sReplaceStr);
                strcat(caNewString, FindPos + strlen(sMatchStr));
                strcpy(sSrc, caNewString);

                FindPos = strstr(sSrc, sMatchStr);
        }

        return 0;
}


－－下面这个函数里使用了内存分配，而且需要调用者来释放
/*C字符串替换函数
调用成功返回指向被替换后新字符串的指针失败返回NULL
调用之后用free()释放*/
char *strrep(char *str,char *str1,char *str2)
{
        char *s;
        unsigned long int len;
        register unsigned long int i=0;
        char *temp;
        temp=str;
        while (strstr(temp,str1)!=NULL){
            temp=strstr(temp,str1)+strlen(str1);
                i++;}
        len=(strlen(temp)-strlen(str1)*i+strlen(str2)*i)*sizeof(char);
        s=(char *)malloc(len);
        if (s!=NULL){
        s="s";
        while (strstr(str,str1)!=NULL)
                {
                s=strncat(s,str,(strstr(str,str1)-str));
                s=strcat(s,str2);
                str=strstr(str,str1)+strlen(str1);}
    s=strcat(s,str);
    s=s+1;
    return(s);}
        else{
                return NULL;}
}


－－下面这个函数只换了一次，不满足
/*
descript:replace str,返回一个替换以后的字符串,用完之后要free()
success:return 1
error:return 0
BUG:"select * from tab where id=':a' and name =':aa'",this is not support,this function is just simple str_replace ,not support all SQL language
*/
char *replacestr(char *strbuf, char *sstr, char *dstr)
{       char *p,*p1;
        int len;

        if ((strbuf == NULL)||(sstr == NULL)||(dstr == NULL))
                return NULL;

        p = strstr(strbuf, sstr);       //返回字符串第一次出现的地址,否则返回NULL
        if (p == NULL)  /*not found*/
                return NULL;

        len = strlen(strbuf) + strlen(dstr) - strlen(sstr);
        p1 = malloc(len);
        bzero(p1, len);
        strncpy(p1, strbuf, p-strbuf);
        strcat(p1, dstr);
        p += strlen(sstr);
        strcat(p1, p);
        return p1;
}