KMP代码
一:C语言:
#include <stdio.h>
void getnext(char *s,int next[])
{/*得到next数据,其实本质是自身KMP匹配*/
int i,j;
i=0;j=-1;next[0]=-1;
while(s[i]){
if(j==-1||s[i]==s[j]){
++i;++j;next[i]=j;
}
else j=next[j];
}
}
int kmp(char *m,char *s,int next[])
{
/*返回s在m中的第一个字母的标*/
int i,j;
i=0;j=0;
while(m[i]){
if(j==-1||m[i]==s[j]){
++i;++j;
if(s[j]=='/0') return (i-j);
}
else j=next[j];
}
return -1;
}
int main()
{
char m[100],s[100];
int next[100];
scanf("%s",s);
getnext(s,next);
scanf("%s",m);
printf("%d",kmp(m,s,next));
getch();
return 0;
}
void getnext(char *s,int next[])
{/*得到next数据,其实本质是自身KMP匹配*/
int i,j;
i=0;j=-1;next[0]=-1;
while(s[i]){
if(j==-1||s[i]==s[j]){
++i;++j;next[i]=j;
}
else j=next[j];
}
}
int kmp(char *m,char *s,int next[])
{
/*返回s在m中的第一个字母的标*/
int i,j;
i=0;j=0;
while(m[i]){
if(j==-1||m[i]==s[j]){
++i;++j;
if(s[j]=='/0') return (i-j);
}
else j=next[j];
}
return -1;
}
int main()
{
char m[100],s[100];
int next[100];
scanf("%s",s);
getnext(s,next);
scanf("%s",m);
printf("%d",kmp(m,s,next));
getch();
return 0;
}
二:C++;
const vector<int> * kmp_next(string &m) // count the longest prefex string ;
{
static vector<int> next(m.size());
next[0]=0; // the initialization of the next[0];
{
static vector<int> next(m.size());
next[0]=0; // the initialization of the next[0];
int temp; // the key iterator......
for(int i=1;i<next.size();i++)
{
temp=next[i-1];
{
temp=next[i-1];
while(m[i]!=m[temp]&&temp>0)
{ temp=next[temp-1];
}
{ temp=next[temp-1];
}
if(m[i]==m[temp])
next[i]=temp+1;
else next[i]=0;
next[i]=temp+1;
else next[i]=0;
}
return &next;
}
bool kmp_search(string text,string m,int &pos)
{
const vector<int> * next=kmp_next(m);
{
const vector<int> * next=kmp_next(m);
int tp=0;
int mp=0; // text pointer and match string pointer;
int mp=0; // text pointer and match string pointer;
for(tp=0;tp<text.size();tp++)
{
while(text[tp]!=m[mp]&&mp)
mp=(*next)[mp-1];
{
while(text[tp]!=m[mp]&&mp)
mp=(*next)[mp-1];
if(text[tp]==m[mp])
mp++;
mp++;
if(mp==m.size())
{ pos=tp-mp+1;
return true;
}
}
{ pos=tp-mp+1;
return true;
}
}
if(tp==text.size())
return false;
}
return false;
}