开发者社区> 问答> 正文

不用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"

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

展开
收起
杨冬芳 2016-03-26 15:06:00 2573 0
1 条回答
写回答
取消 提交回答
  • IT从业

    假设已经有一个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;
    }
    2019-07-17 19:16:17
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

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

相关实验场景

更多