(C语言)BF算法、KMP算法 :删除子串、查找子串位置——初学者的举一反三
2021/12/26 22:11:12
本文主要是介绍(C语言)BF算法、KMP算法 :删除子串、查找子串位置——初学者的举一反三,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
作为初学者,要学会举一反三,才能更好的掌握
今日看到一题squeeze: delete all characters stored in variable c from string s
题目很简单,删除s中的所有字符
函数接口定义:
void squeeze(char s[], int c);
裁判测试程序样例:
#include <stdio.h> void squeeze(char s[], int c); /* the length of a string */ int main(){ char s[100]; char c; int i; scanf("%s %c", s, &c); squeeze(s, c); for (i = 0; s[i] != '\0'; i++) putchar(s[i]); putchar('\n'); return 0; } /* 请在这里填写答案 */
题解:
void squeeze(char s[], int c) { int i, j; for (i = j = 0; s[i] != '\0'; ++i) if (s[i] != c) s[j++] = s[i]; s[j] = '\0'; }
但如果是删除一个子串呢?
可以用BF算法或KMP算法解决
在这里我用BF算法删除一个子串,KMP算法找到子串位置
BF算法:
#include <string.h> #include <stdio.h> int squeeze(char s1[], char s2[]); int main(){ char s1[100]; char s2[100]; int i; int index; scanf("%s %s", s1, s2); index = squeeze(s1,s2); for (i = index;i<=strlen(s2) && s1[i+strlen(s2)]!='\0';i++) { s1[i] = s1[i+strlen(s2)]; } s1[i] = '\0'; for (i = 0; s1[i] != '\0'; i++) putchar(s1[i]); putchar('\n'); return 0; } int squeeze(char s1[],char s2[]) { int i = 0,j = 0; while(i<strlen(s1) && j<strlen(s2)) { if(s1[i] == s2[j]){ ++i; ++j; } else{ i = i-j+1; j = 0;//重新指向子串第一个 } } if(j>=strlen(s2)) { return i-strlen(s2);//返回子串位置 } else return -1; }
KMP算法:
#include <string.h> #include <stdio.h> int squeeze(char s1[], char s2[]); void getnext(char s2[]); int next[50] = {0}; int main(){ char s1[100]; char s2[100]; int i; int index; scanf("%s %s", s1, s2); getnext(s2); index = squeeze(s1,s2); printf("%d",index); return 0; } int squeeze(char s1[],char s2[]) { int i = 0,j = 0; int len1,len2; len1 = strlen(s1); len2 = strlen(s2); while(i<len1 &&j<len2) { if(j==-1 || s1[i] == s2[j]) { i++; j++; } else j = next[j]; } if(j>=len2)return i-len2; else return -1; } void getnext(char s2[]) { int i = 2,j = 0; next[0] = -1; next[1] = 0; while(i<strlen(s2)) { if(j==-1 || s2[j]==s2[i-1]) { next[i] = j+1; ++i; ++j; } else j = next[j]; } }
这篇关于(C语言)BF算法、KMP算法 :删除子串、查找子串位置——初学者的举一反三的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享