#include"stdio.h"
#define maxsize 20
typedef struct
{
char date[maxsize+1];
int length;
}sstring;
typedef struct sqlink
{
char *date;
int length;
}hstring;
void init(hstring *t)
{
t->date=new char[6];
}
void next1(hstring t,int next[])
{
int i,j;
i=1;next[1]=0;j=0;
while(i<t.length)
{
if(j=0||t.date[i]==t.date[j])
{
i++;j++;next[i]=j;
}
else
j=next[j];
}
}
int kmp(sstring s,hstring t,int next[])
{
int i=1,j=1;
while(i<=s.length&&j<=t.length)
{
if(j==0||s.date[i]==t.date[j])
{
i++;j++;
}
else
j=next[j];
}
if(j>t.length)
return i-t.length;
else
return 0;
}
int main()
{
char ch;int i=1,next[6];
sstring s;hstring t;
s.length=t.length=0;
init(&t);
ch=getchar();
while(ch!='#')
{
s.date[i]=ch;
s.length++; i++;
}
ch=getchar();i=1;
while(ch!='#')
{
t.date[i]=ch;
t.length++;
}
next1(t,next);
printf("%d\n",kmp(s,t,next));
}
这种字符串算法就不要自己实现了,太浪费时间了,找个现成的看看就行了。