串的模式匹配
1.串的模式匹配---BF算法
typedef struct
{
char data[MaxSize];//存放串字符
int length; //存放串长
}SqString; //顺序串类型
int index(SqString s,SqString t)
{
int i=0,j=0;
while(i<s.length && j<t.length)
{
if(s.data[i]==s.data[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j>=t.length)
return (i-t.length);
else
return (-1);
}
2.串的模式匹配---KMP算法
typedef struct
{
char data[MaxSize];//存放串字符
int length; //存放串长
}SqString; //顺序串类型
void GetNext(SqString t,int next[])//对模式串t求next[]值
{
int j,k;
j=0;k=-1;next[0]=-1;
while(j<t.length-1)
{
if(k==-1 || t.data[j]==t.data[k])//k为-1或者比较的字符相等时
{
j++;k++;
next[j]=k;
}
else k=next[k];
}
}
int KMPIndex(SqString s,SqString t)
{
int next[MaxSize],i=0,j=0;
GetNext(t,next);
while(i<s.length && j<t.length)
{
if(j==-1 || s.data[i]==t.data[j])
{
i++; //i,j各增1
j++;
}
else j=next[j]; //i不变，j后退
}
if(j>=t.length)
return (i-t.length); //返回匹配模式串中首字母下标
else
return (-1); //返回不匹配标志
}
3.串的模式匹配---修正后nextval+KMP算法
typedef struct
{
char data[MaxSize];//存放串字符
int length; //存放串长
}SqString; //顺序串类型
void GetNextval(SqString s,SqString t)
{
int j=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,SqString t)
{
int nextval[MaxSize],i=0,j=0;
GetNextval(t,next);
while(i<s.length && j<t.length)
{
if(j==-1 || s.data[i]==t.data[j])
{
i++; //i,j各增1
j++;
}
else j=next[j]; //i不变，j后退
}
if(j>=t.length)
return (i-t.length); //返回匹配模式串中首字母下标
else
return (-1); //返回不匹配标志
}