#include
using namespace std;
const int MAXLEN=255;
typedef struct{
char ch[MAXLEN+1];
int length;
}SString;
void get_next(SString T,int next[])
{
int i=1;
next[1]=0;
int j=0;
while(iif( j==0 || T.ch[i]==T.ch[j])
{
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
int Index_KMP(SString S,SString T,int pos)
{
int i=pos;
int j=1;
int next[256];
get_next(T, next);
while(i<=S.length&&j<=T.length)
{
if(j==0||S.ch[i]==T.ch[j])
{
++i;
++j;
}
else
j=next[j];
}
if(j>T.length)
return i-T.length;
else
return 0;
}
int main()
{
SString S,T;
int n,m;
cout<<"输入主串串长:";
cin>>n;
cout<<"输入主串:";
for(int i=1;i<=n;i++)
{
cin>>S.ch[i];
}
cout<<"输入模式串串长:";
cin>>m;
cout<<"输入模式串:";
for(int k=1;k<=m;k++)
{
cin>>T.ch[k];
}
cout<;
int pos;
cout<<"输入匹配的位置:";
cin>>pos;
if(Index_KMP(S,T,pos)!=0)
cout<<"匹配成功,模式串在主串中的位置是:"<pos);
else
cout<<"匹配失败,模式串不在主串中"<;
return 0;
}