开发者社区> 问答> 正文

不用string库实现字符串替换

当然复杂度越低越好.

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"

展开
收起
a123456678 2016-06-02 20:55:21 2377 0
1 条回答
写回答
取消 提交回答
  • #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;
    }
    2019-07-17 19:25:37
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载

相关实验场景

更多