每日一练--C语言--串

目标

实现串的经典模式匹配算法与KMP算法。

简述

自定义串结构； 串采用定长顺序存储结构，串从下标1开始存储，0下标存储串的实际长度； 匹配成功返回匹配位置，匹配失败返回0。

#include <stdio.h> #define MAXLENTH 255 typedef unsigned char String[MAXLENTH+1]; //0下标存储字符串长度 int Index(String,String,int); int Index_KMP(String,String,int,int *); int main() { int i,j; String S=" abcdabcabcdeaabcaacccceeeeacdbcd"; //开头空格为跳过下标0赋值 S[0]=sizeof(" abcdabcabcdeaabcaacccceeeeacdbcd")-2; String T=" abca"; T[0]=sizeof(" abca")-2; int Next[T[0]+1]; Next[0]=0; i=Index(S,T,1); j=Index_KMP(S,T,1,Next); printf("The Index function return %d.\n",i); printf("The Index_KMP function return %d.\n",j); return 0; } int Index(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0]&&j<=T[0]){ if(S[i]==T[j]){ i++; j++; }else{ i=i-j+2; j=1; } } if(j>T[0]) return i-j+1; else return 0; } int Index_KMP(String S,String T,int pos,int *Next) //用Next[0]标志是否已生成所需Next数组 { int i,j; if(!Next[0]){ i=1; j=0; Next[1]=0; while(i<T[0]){ if(j==0||T[i]==T[j]){ i++; j++; if(T[i]==T[j]) Next[i]=Next[j]; else Next[i]=j; }else j=Next[j]; } if(i>=T[0]) Next[0]=1; } i=pos,j=1; while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){ i++; j++; }else{ j=Next[j]; } } if(j>T[0]) return i-j+1; else return 0; }

转载于:https://www.cnblogs.com/jerehao/p/5553945.html