爱华网顺序串的各种模式匹配运算
编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：
（1）建立“abcabcdabcdeabcdefabcdefg”目标串s和“abcdeabcdefab”模式串t。
（2）采用简单匹配算法求t在s中的位置。
（3）由模式串t求出next值和nextval值。
（4）采用KMP算法求t在s中的位置。
（5）采用改进的KMP算法求t在s中的位置。
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define MaxSize 100
typedef struct {
chardata[MaxSize];//定义可容纳MaxSize个字符的空间
intlength;//标记当前实际串长
}SqString;
void StrAssign(SqString &str,charcstr[]){ //由串常量cstr创建串str
int i;
for(i=0;cstr[i]!=' ';i++)
str.data[i]=cstr[i];
str.length=i;
}
void DispStr(SqStrings){ //输出串s的所有元素
int i;
if(s.length>0){
for(i=0;i<s.length;i++)
printf("%c",s.data[i]);
printf("n");
}
}
int Index(SqString s,SqStringt){//简单匹配算法
inti=0,j=0,k;
while(i<s.length &&j<t.length){
if(s.data[i]==t.data[j]){//继续匹配下一个字符
i++;
j++;
}else{//主串、子串指针回溯重新开始下一次匹配
i=i-j+1;
j=0;
}
}
if(j>=t.length)
k=i-t.length;//返回匹配的第一个字符的下标
else
k=-1;//模式匹配不成功
returnk;
}
void GetNext(SqString t,intnext[]){//由模式串t求出next值
intj,k;
j=0;
k=-1;next[0]=-1;
while(j<t.length-1){
if(k==-1 || t.data[j]==t.data[k]){
j++;
k++;
next[j]=k;
}else
k=next[k];
}
}
void GetNextval(SqString t,intnextval[]){//由模式串t求出nextval值
intj=0,k=-1;
nextval[0]=-1;
while(j<t.length){
if(k==-1 || t.data[j]==t.data[k]){
j++;
k++;
if(t.data[j]!=t.data[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}else
k=nextval[k];
}
}
int KMPIndex(SqString s,SqStringt){//KMP算法
intnext[MaxSize],i=0,j=0,v;
GetNext(t,next);
while(i<s.length &&j<t.length){
if(j==-1 || s.data[i]==t.data[j]){
i++;
j++;
}else
j=next[j]; //i不变，j后退
}
if(j>=t.length)
v=i-t.length;//返回匹配模式串的首字符下标
else
v=-1;//返回不匹配标志
returnv;
}
int KMPIndex1(SqString s,SqStringt){ //改进的KMP算法
intnextval[MaxSize],next[MaxSize],i=0,j=0,v;
GetNextval(t,next);
GetNextval(t,nextval);
while(i<s.length &&j<t.length){
if(j==-1 || s.data[i]==t.data[j]){
i++;
j++;
}else
j=nextval[j];
}
if(j>=t.length)
v=i-t.length;//返回匹配模式串的首字符下标
else
v=-1;
returnv;
}
int main(){
int j;
intnext[MaxSize],nextval[MaxSize];
SqStrings,t;
StrAssign(s,"abcabcdabcdeabcdefabcdefg");
StrAssign(t,"abcdeabcdefab");
printf("串s:");DispStr(s);
printf("串t:");DispStr(t);
printf("简单匹配P算法:n");
printf(" t在s中的位置=%dn",Index(s,t));
GetNext(t,next);//由模式串t求出next值
GetNextval(t,nextval); //由模式串t求出nextval值
printf("j ");
for(j=0;j<t.length;j++)
printf("M",j);
printf("n");
printf("t[j] ");
for(j=0;j<t.length;j++)
printf("L",t.data[j]);
printf("n");
printf("next ");
for(j=0;j<t.length;j++)
printf("M",next[j]);
printf("n");
printf("nextval");
for(j=0;j<t.length;j++)
printf("M",nextval[j]);
printf("n");
printf("KMP算法：n");
printf(" t在s中的位置=%dn",KMPIndex(s,t));
printf("改进的KMP算法：n");
printf(" t在s中的位置=%dn",KMPIndex1(s,t));
return0;
}
