#include<iostream>
using namespace std;
#define M 1000
//int kmp(char *t,char *p,int pos)
int kmp(char *t,char *p)
{
//p模式串，t主串
//預處理
int next[M];
//memset(next,0,sizeof(next));
int i,j,
lent=strlen(t),
lenp=strlen(p);
next[0]=-1;
i=0;j=-1;
while(i<lenp-1)
{
if(j==-1 || p[i]==p[j])
{
++i;++j;
if(p[i]!=p[j]) next[i]=j;
else next[i]=next[j];
//next[i]=j;
}
else j=next[j];
}
//匹配
i=0;j=0;
while(i<lent && j<lenp)
{
if(j==-1 || t[i]==p[j]) {++i;++j;}
else j=next[j];
}
if(j==lenp) return i-lenp;
else return -1;
}
int main()
{
char t[100],p[100];
while(cin>>t>>p)
cout<<kmp(t,p)<<endl;
return 0;
}
//
posted on 2009-07-30 17:22
wyiu 閱讀(174)
評論(0) 編輯 收藏 引用 所屬分類:
常用模板和函數