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; }
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; }
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; }