模式匹配的几种算法(含KMP算法)
#include<stdio.h> #include<string.h> #include<stdlib.h> int failure[100];//失配函数 int strmatch_bf(char *s,char *t) { //简单模式匹配,基本思想:将s和t进行比较,如果相等继续比较,否则t从头开始,s从i-j+1开始 int i,j; i=j=0; while((i < int(strlen(s))) && (j < int(strlen(t)))) { if(s[i]==t[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j>=int(strlen(t))) return strlen(s)-i; else return -1; } int endmatch(char *s,char *t) {//先检测末端标记的模式匹配方法 int i,j,start=0; int lasts=strlen(s)-1; int lastt=strlen(t)-1; int end=lastt; for(i=0;end<=lasts;end++,start++) { if(s[end]==t[lastt]) for(j=0,i=start;j<lastt&&s[i]==t[j];i++,j++); if(j==lastt) return start;//匹配成功 } return -1; } int pmatch_kmp(char *string,char *pat) { int i=0,j=0; int lens=strlen(string); int lenp=strlen(pat); while(i<lens&&j<lenp) { if(string[i]==pat[j]) { i++;j++; } else if(j==0) i++; else j=failure[j-1]+1; } return ((j==lenp)?(i-lenp):-1); } void fail(char *pat) { int n=strlen(pat); int i,j; failure[0]=-1; for(j=1;j<n;j++) { i=failure[j-1]; while((pat[j]!=pat[i+1])&&(i>=0)) i=failure[i]; if(pat[j]==pat[i+1]) failure[j]=i+1; else failure[j]=-1; } } int main() { int x; char s[100],t[100]; scanf("%s",s); scanf("%s",t); fail(t); x=strmatch_bf(s,t); printf("%d\n",x); x=endmatch(s,t); printf("%d\n",x); x= pmatch_kmp(s,t); printf("%d\n",x); return 0; } #include<stdio.h> #include<string.h> #include<stdlib.h> int failure[100];//失配函数 int strmatch_bf(char *s,char *t) { //简单模式匹配,基本思想:将s和t进行比较,如果相等继续比较,否则t从头开始,s从i-j+1开始 int i,j; i=j=0; while((i < int(strlen(s))) && (j < int(strlen(t)))) { if(s[i]==t[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j>=int(strlen(t))) return strlen(s)-i; else return -1; } int endmatch(char *s,char *t) {//先检测末端标记的模式匹配方法 int i,j,start=0; int lasts=strlen(s)-1; int lastt=strlen(t)-1; int end=lastt; for(i=0;end<=lasts;end++,start++) { if(s[end]==t[lastt]) for(j=0,i=start;j<lastt&&s[i]==t[j];i++,j++); if(j==lastt) return start;//匹配成功 } return -1; } int pmatch_kmp(char *string,char *pat) { int i=0,j=0; int lens=strlen(string); int lenp=strlen(pat); while(i<lens&&j<lenp) { if(string[i]==pat[j]) { i++;j++; } else if(j==0) i++; else j=failure[j-1]+1; } return ((j==lenp)?(i-lenp):-1); } void fail(char *pat) { int n=strlen(pat); int i,j; failure[0]=-1; for(j=1;j<n;j++) { i=failure[j-1]; while((pat[j]!=pat[i+1])&&(i>=0)) i=failure[i]; if(pat[j]==pat[i+1]) failure[j]=i+1; else failure[j]=-1; } } int main() { int x; char s[100],t[100]; scanf("%s",s); scanf("%s",t); fail(t); x=strmatch_bf(s,t); printf("%d\n",x); x=endmatch(s,t); printf("%d\n",x); x= pmatch_kmp(s,t); printf("%d\n",x); return 0; }
补充:移动开发 , Android ,