#include <stdio.h>
#include <malloc.h>
#include <string.h>
 
char* replaceAll(char* src, char* find, char* replaceWith){
    //如果find或者replace为null，则返回和src一样的字符串。
    if(find == NULL || replaceWith == NULL){
        return strdup(src);
    }
    //指向替换后的字符串的head。
    char* afterReplaceHead = NULL;
    //总是指向新字符串的结尾位置。
    char* afterReplaceIndex = NULL;
    //find字符串在src字符串中出现的次数
    int count = 0;
    int i,j,k;
     
    int srcLen = strlen(src);
    int findLen = strlen(find);
    int replaceWithLen = strlen(replaceWith);
     
    //指向src字符串的某个位置，从该位置开始复制子字符串到afterReplaceIndex，初始从src的head开始复制。
    char* srcIndex = src;
    //src字符串的某个下标，从该下标开始复制字符串到afterReplaceIndex，初始为src的第一个字符。
    int cpStrStart = 0;
    
    //获取find字符串在src字符串中出现的次数
    count = getFindStrCount(src, find);
    //如果没有出现，则返回和src一样的字符串。
    if(count == 0){
        return strdup(src);
    }
     
    //为新字符串申请内存
    afterReplaceHead = afterReplaceIndex = (char*)malloc(srcLen + 1 + (replaceWithLen - findLen) * count);
    //初始化新字符串内存
    memset(afterReplaceHead, '\0',sizeof(afterReplaceHead));
 
    for(i = 0,j = 0,k = 0;i!=srcLen;i++){
        //如果find字符串的字符和src中字符串的字符是否相同。
        if(src[i] == find[j]){
            //如果刚开始比较，则将i的值先赋给k保存。
            if(j == 0){
                k = i;
            }
            //如果find字符串包含在src字符串中
            if(j == (findLen-1)){
                j = 0;
                //拷贝src中find字符串之前的字符串到新字符串中
                strncpy(afterReplaceIndex, srcIndex, i - findLen - cpStrStart + 1);
                //修改afterReplaceIndex
                afterReplaceIndex = afterReplaceIndex + i - findLen - cpStrStart + 1;
                //修改srcIndex
                srcIndex = srcIndex + i - findLen - cpStrStart + 1;
                //cpStrStart
                cpStrStart = i + 1;            
 
                //拷贝replaceWith字符串到新字符串中
                strncpy(afterReplaceIndex, replaceWith, replaceWithLen);
                //修改afterReplaceIndex
                afterReplaceIndex = afterReplaceIndex + replaceWithLen;
                //修改srcIndex
                srcIndex = srcIndex + findLen;
            }else{
                j++;
            }
        }else{
            //如果find和src比较过程中出现不相等的情况，则将保存的k值还给i
            if(j != 0){
                i = k;
            }
            j = 0;
        }
    }
    //最后将src中最后一个与find匹配的字符串后面的字符串复制到新字符串中。
    strncpy(afterReplaceIndex, srcIndex, i - cpStrStart);
     
    return afterReplaceHead;
}
 
int getFindStrCount(char* src, char* find){
    int count = 0;
    char* position =src;
    int findLen = strlen(find);
    while((position = strstr(position, find)) != NULL){
        count++;
        position = position + findLen;
    }
    return count;
}
 
int main(void){
    char* s = "12345345443344341334542345";
    //调用函数replaceAll，s为源字符串，"345"为需要替换的字符串，”7890“为替换目的字符串。
    char* r = replaceAll(s, "345", "7890");
    printf("%s\n",r);
    //使用replaceAll函数后一定要free掉，因为replace内部会malloc结果字符串的内存。
    free(r);
    return 0;
}