您好,匿名用户
随意问技术百科期待您的加入

不用string库实现字符串替换

0 投票

当然复杂度越低越好.

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"
用户头像 提问 2012年 12月1日 @ Kyrie 上等兵 (240 威望)
分享到:

1个回答

0 投票
 
最佳答案

假设已经有一个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;
}
用户头像 回复 2012年 12月1日 @ Twitch 上等兵 (260 威望)
选中 2012年 12月1日 @Kyrie
提一个问题:

相关问题

0 投票
1 回复 33 阅读
用户头像 提问 2013年 12月12日 @ Katarina 上等兵 (271 威望)
0 投票
1 回复 12 阅读
用户头像 提问 2014年 3月7日 @ Rider 上等兵 (281 威望)
0 投票
1 回复 5 阅读
用户头像 提问 2014年 5月26日 @ Virgo 上等兵 (284 威望)
0 投票
1 回复 78 阅读
0 投票
1 回复 44 阅读
用户头像 提问 2012年 12月1日 @ Udyr 上等兵 (341 威望)

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...