c语言KMP匹配算法与字符串替换算法
2022/6/11 1:22:42
本文主要是介绍c语言KMP匹配算法与字符串替换算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一.字符串匹配算法
(1)传统匹配算法BF
int Index_BF(char* S, char* T){ int i=1,j=1; while(i<=strlen(S) && j<=strlen(T)){ if(S[i]==T[j]){ ++i; ++j; } else{ i=i-j+2; j=1; } } if(j>strlen(T)) return i - strlen(T); else return 0; }
(2)KMP
void get_next(char* T, int next[]){ int i=1,j=0; next[1]=0; while(i<strlen(T)){ if(j==0||T[i]==T[j]){ ++i; ++j; next[i]=j; } else j=next[j]; } } int Index_KMP(char* S, char* T, int next[]){ int i=1, j=1; while (i<=strlen(S)&&j<=strlen(T)){ if(j==0||S[i]==T[j]){ ++i; ++j; } else j=next[j]; } if(j>strlen(T)) return i-strlen(T); else return 0; }
(3)KMP改进算法
void get_nextval(char* T,int nextval[]){ int i=1,j=0; nextval[1]=0; while(i<strlen(T)){ if(j==0||T[i]==T[j]){ ++i; ++j; if(T[i]!=T[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } }
以上为基本算法函数;
以下是完整程序,同时可以展现匹配过程:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include<cstring> #include<iostream> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; #define MAXSTRLEN 255 //用户可在255以内定义最长串长 typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度 Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T int i; if (strlen(chars) > MAXSTRLEN) return ERROR; else { T[0] = strlen(chars); for (i = 1; i <= T[0]; i++) T[i] = *(chars + i - 1); return OK; } } void get_next(SString T, int next[]){ //求模式串T的next函数值并存入数组next int i = 1, j = 0; next[1] = 0; while (i < T[0]) if (j == 0 || T[i] == T[j]) { ++i; ++j; next[i] = j; }//abssgaaadaaaadcf aaaad 0 else j = next[j]; for(i=1;i<strlen(T);i++) printf("j=%d next[%d]=%d \n",i,i,next[i]);//abssgaaadaaaadcf aaaad 0 }//get_next void get_nextval(SString T, int nextval[]){ // 求模式串T的next函数修正值并存入数组nextval int i = 1, j = 0; nextval[1] = 0; while (i < T[0]) if (j == 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; for(i=1;i<strlen(T);i++) printf("j=%d nextval[%d]=%d \n",i,i,nextval[i]); }//get_nextval // void BF(char s[100],char p[50],int t){ int space,a,b,k=0,num=0; int pos, i, j, flag; j = flag = 0; if(strlen(s)<strlen(p)){ printf("Error:子串长度大于父串.\n"); return ; } if(strlen(s)-strlen(p)<t){ printf("Error:匹配位置不合适.\n"); return ; } space=i=pos=t; printf("\n"); while(i < strlen(s)) { if(j==0&&s[i]!=p[j]) num++; pos=i; if(p[j] == s[i]){ while(j < strlen(p)) { if(p[j] != s[i]) { k++; printf("%s %d 此次匹配失败\n",s,k); for(a=space;a>0;a--) printf(" ");//输出详细过程 for(b=0;b<=j;b++) printf("%c",p[b]);//aaadddawawdcw awd 0 printf("\n"); break; } else{ k++; printf("%s %d 此次匹配成功\n",s,k); for(a=space;a>0;a--) printf(" ");//输出详细过程 for(b=0;b<=j;b++) printf("%c",p[b]); printf("\n"); i++; j++; } } if(j == strlen(p)) flag = 1; } else{ k++; printf("%s %d 此次匹配失败\n",s,k);//aaadddawawdcw awd 0 for(a=space;a>0;a--) printf(" "); printf("%c\n",p[j]) ; } space++; if(flag == 1){//如果匹配成功,flag=1,则进入此句; printf("匹配位置为:%d\n", pos); break; } //开始下一轮的循环,对某些变量进行初始化 i = ++pos; j = 0; if(i > strlen(s) - strlen(p)){ printf("主串中不存在此子串!\n"); break; } } printf("共匹配%d次\n",k); printf("单个字符匹配次数为%d\n",num); } int KMP(SString S, SString T, char* s, char* p, int pos, int next[]){ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法 //其中,T非空,1≤pos≤StrLength(S) if(strlen(s)<strlen(p)){ printf("Error:子串长度大于父串.\n"); return -1; } if(strlen(s)-strlen(p)<pos){ printf("Error:匹配位置不合适.\n"); return -1; } int i = pos, j = 1,k=0,a,b,space=0; while (i <= S[0] && j <= T[0]) { if (j == 0 || S[i] == T[j]) // 继续比较后继字 { i++; j++; if(j == strlen(T)) { // 进入此if语句即表示匹配成功 printf("共循环%d次\n",k); break; } ++k; printf("%s %d next[%d]=%d \n",s,k,j,next[j]); for(a=space;a>0;a--) printf(" "); for(b=1;b<=j;b++) printf("%c",T[b]);//abssgaaadaaaadcf aaaad 0 printf("\n"); if(j==1&&S[i]!=T[j]) simple++;//记录单字符匹配失败的次数。 } else j = next[j];// 模式串向右移动 space=i-j; //输出子串前面的空格数 } printf("单字符循环%d次\n",simple); if (j > T[0]) // 匹配成功 return i - T[0]; else return -1; }//Index_KMP int main(){ printf("1.输入主串、子串和匹配起始位置\n2.BF算法\n3.KMP算法\n4.KMP改进算法\n0.退出\n"); int t = -1,place; SString S;//abssgaaadaaaadcf aaaad 0 SString T; int *next,*nextval; char s[50], p[50]; while(t) { printf("请输入:"); scanf("%d",&t); switch(t) { case 0: break; case 1: printf("请输入主串、子串和匹配起始位置:\n"); scanf("%s%s%d",s,p,&place); StrAssign(S,s) ; StrAssign(T,p) ; break; case 2: BF(s,p,place); break; case 3: next = new int[T[0]+1]; get_next(T,next); printf("匹配的位置为 %d\n",KMP(S,T,s,p,place,next)); break; case 4: nextval = new int[T[0]+1]; get_nextval(T,nextval) ; printf("匹配的位置为 %d\n",KMP(S,T,s,p,place,nextval)); break; default: break; } } return 0; }
二.字符串替换算法
#include<stdio.h> #include<string.h> #include<stdlib.h> char* str_replace(char* str,char* oldstr,char* newstr){ char bstr[strlen(str)];//转换缓冲区 memset(bstr,0,sizeof(bstr)); for(int i=0; i<strlen(str); i++){ if(!strncmp(str+i,oldstr,strlen(oldstr))){//查找目标字符串 strcat(bstr,newstr); i = i + strlen(oldstr) - 1; }else{ strncat(bstr,str+i,1);//保存一字节进缓冲区 } } char tmp[strlen(str)*2]; strcpy(tmp,bstr); return tmp; }
这篇关于c语言KMP匹配算法与字符串替换算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升