不用string库实现字符串替换

假设已经有一个kmp函数，返回substr在str中出现的位置，如果不存在则返回NULL（行为和strstr一样）。

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

const char *kmp(const char *str, const char *substr)
{
    return strstr(str, substr); //kmp的实现略过
}

void str_replace(char *dest, const char *src, 
        const char *pattern, const char *replace)
{
    int lp = strlen(pattern), lr = strlen(replace);
    const char *temp = src, *last = src;
    while ((temp = kmp(temp, pattern)) != NULL)
    {
        //copy to dest
        memcpy(dest, last, temp - last);
        dest += temp - last;

        strcpy(dest, replace);
        dest += lr;

        temp += lp;
        last = temp;
    }
    strcpy(dest, last);
}

int main()
{
    char dest[1000];
    str_replace(dest, "abcdefgabcdefgabcdefg", "fg", "----");
    printf("%s\n", dest);

    str_replace(dest, "abcdefgabcdefgabcdefg", "ef", "----");
    printf("%s\n", dest);

    str_replace(dest, "hello world", "l", "ab");
    printf("%s\n", dest);
    return 0;
}

算法其实挺简单，接口的设计，得写额外的代码来计算需要多大的空间，上面就略过了，另外附一个由函数负责分配空间的安全版（相应的后果是要额外扫一遍）：

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

const char *kmp(const char *str, const char *substr)
{
    return strstr(str, substr);
}

char *str_replace(const char *src, const char *pattern, const char *replace)
{
    int count = 0, lp = strlen(pattern), lr = strlen(replace);
    char *dest = NULL, *ret = NULL;
    const char *temp = src, *last = NULL;
    while ((temp = kmp(temp, pattern)) != NULL)
    {
        count++;
        temp += lp;
    }

    dest = ret = (char *)malloc(sizeof(lr - lp) * count + strlen(src) + 1);
    if (ret == NULL) 
        return NULL;

    temp = src, last = src;
    while ((temp = kmp(temp, pattern)) != NULL)
    {
        //copy to dest
        memcpy(dest, last, temp - last);
        dest += temp - last;

        strcpy(dest, replace);
        dest += lr;

        temp += lp;
        last = temp;
    }
    strcpy(dest, last);
    return ret;
}

int main()
{
    char *dest = NULL;
    dest = str_replace("abcdefgabcdefgabcdefg", "fg", "----");
    if (dest != NULL)
        printf("%s\n", dest);
    free(dest);

    dest = str_replace("abcdefgabcdefgabcdefg", "ef", "----");
    if (dest != NULL)
        printf("%s\n", dest);
    free(dest);

    dest = str_replace("hello world", "l", "ab");
    if (dest != NULL)
        printf("%s\n", dest);
    free(dest);
    return 0;
}