不用string库实现字符串替换-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

不用string库实现字符串替换

2016-03-26 15:06:00 2198 1

当然复杂度越低越好.
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一样)。

取消 提交回答
全部回答(1)
  • 杨冬芳
    2019-07-17 19:16:17

    假设已经有一个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;
    }
    0 0
相关问答

1

回答

Java中string是什么呀?

2022-04-02 21:33:15 325浏览量 回答数 1

1

回答

Java里String字符串equals和equalsIgnoreCase的区别有哪些呀?

2022-04-02 21:41:38 390浏览量 回答数 1

1

回答

Java中String类常用的构造方法有哪些?

2022-04-02 21:47:25 332浏览量 回答数 1

1

回答

Java里String字符串获取功能的方法有哪些呀?

2022-04-02 21:55:36 347浏览量 回答数 1

1

回答

Java中String 字符串的创建形式有哪些呀?

2022-04-02 22:02:32 354浏览量 回答数 1

1

回答

Java String equals() 方法的返回值是什么?

2021-11-18 21:49:30 167浏览量 回答数 1

1

回答

Java String equals() 方法的语法是什么?

2021-11-18 21:48:33 146浏览量 回答数 1

1

回答

JAVA中 switch 支持 String 与枚举如何理解?

2021-11-17 23:33:21 297浏览量 回答数 1

1

回答

java中String getHostName() 是什么?

2021-11-17 18:26:58 130浏览量 回答数 1

1

回答

java中String getHostAddress() 是什么?

2021-11-17 18:26:57 97浏览量 回答数 1
+关注
杨冬芳
IT从业
文章
问答
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载