目标
实现串的经典模式匹配算法与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;
}