这个模式匹配怎么做？没头文件，怎样编辑头文件呢？ 串KMP算法的C语言实现： #include
发布网友
发布时间：2022-05-26 12:28
共1个回答
热心网友
时间：2023-10-17 00:41
#include <stdlib.h>
#include "sqstring.h"
void main()
{
SqString s,t;
StrAssign(s,"ababcabcacbab");
StrAssign(t,"abcac");
printf("s:");DispStr(s);
printf("t:");DispStr(t);
printf("位置:%d\n",KMPIndex(s,t));
system("pause");
}
/*头文件实现*/
/*头文件文件名：sqstring.h */
/*头文件程序部分*/
#ifndef INCL_SQSTRING_H /*和头文件匹配*/
#define INCL_SQSTRING_H
void GetNext(SqString t,int next[]) /*由模式串t求出next值*/
{
int j,k;
j=0;k=-1;next[0]=-1;
while (j<t.len-1)
{
if (k==-1 || t.data[j]==t.data[k]) /*k为-1或比较的字符相等时*/
{
j++;k++;
next[j]=k;
}
else k=next[k];
}
}
/*KMPIndex实现*/
int KMPIndex(SqString s,SqString t)
{
int next[100];
int i,j;
i=0;
j=0;
getNext(t,next);
while(i<strlen(s))
{
if(j==-1||s[i]==t[j])
{
i++;
j++;
}
else
{
j=next[j]; //消除了指针i的回溯
}
if(j==strlen(t))
return i-strlen(t);
}
return -1;
}
#endif
