不用string库实现字符串替换

Question

当然复杂度越低越好.

strstr的O(m+n)实现也是比较困难.不过已经有解决的办法(kmp)

现在我们想解决一个strrp函数.最低的复杂度应该是O(m+n+k) 吧

最好不用库函数.

好吧,其实我思考了一段时间了. 声明啊:this not my homework.. i do it for good solutions but not for tasks..

难度有点高.大家一起找好算法..

sample input:

src="hello world"   //source string
sub_str="l"   //to be replaced
rpl_with="ab" //replace with

output should be:

"heababo worabd"

Answer 1

假设已经有一个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;
}

p.s. 里面虽然用到了 memcpy, strlen, strcpy，但是这些自己额外写都是很简单的。

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

#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;
}