谢谢！

明白了

#include <iostream>
using namespace std;

void get_next(char *c,int *i);
int Index_KMP(char* s,char* T,int pos);

int main()
{
char c[100],d[100];
int b[100];
scanf("%s %s",c,d);
int i,j;
i=Index_KMP(c,d,1);
printf("i=%d\n",i);
return 0;
}

void get_next(char *c,int *next)
{
int i,len,j;
next[0]=-1;
i=0;
j=-1;
len=strlen(c);
while(i<len-1)
{
if(j==-1||c[i]==c[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}
}

int Index_KMP(char* s,char* T,int pos)
{
int j=0,i=0,*p;
p=new int[strlen(T)];
get_next(T,p);
j=0;
//while((j!=strlen(T))&&(i!=strlen(s)))
int lent=strlen(T);
int lens=strlen(s);
while((j<lent)&&(i<lens))
{
if(j==-1)
{
i++;
j++;
}
else if(T[j]==s[i])
{
i++;
j++;
}
else
j=p[j];
}
if(j==strlen(T))
return i-strlen(T)+1;
return -1;
}

你能帮我解释一下为什么这样就可以了么 谢谢！

/*---------------------------------------------------------------------------
File name: kmp.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 10/13/2007 18:54:23
Environment: WinXPSP2 En Pro + VS2005 v8.0.50727.762

All indices start from 0, not 1.

O(n, m) means O(n) time, O(m) space.
O(n) means O(n) time, O(1) space.
*/

#include <iostream>
using namespace std;

/** Need to check boundary conditions, such as t=NULL, strlen(t)=0, etc.

Algorithm 4.5 (Yan, Weimin, P 79)

O(n*m).
*/
char* substr(char* s, char* t, int pos)
{
char* p = s+pos, * q = t;
int c=0, m=strlen(t);

while(*p && c<m)
{
if(*p==*q)
{
++p;
++q;
++c;
}
else
{
p+=1-c;
q=t;
c=0;
}
}

if(c==m)
{
return p-c;
}
else
{
return NULL;
}
}

/** Compute the next[] table.
Algorithm 4.8 (Yan, Weimin, P 84)

O(m, m).
*/
void get_nextval(char* t, int*& nextval)
{
int m=strlen(t)-1, j=-1, i=0;

nextval[0]=-1;
while(i<m)
{
if(j==-1 || t[i]==t[j])
{
++i;
++j;
if(t[i]==t[j])
{
nextval[i] = nextval[j];
}
else
{
nextval[i] = j;
}
}
else
{
j=nextval[j];
}
}
}

/** Implement the KMP string matching algorithm.

Algorithm 4.6 (Yan, Weimin, P 82)

O(n+m, m).
*/
char *substr_kmp(char* s, char* t, int pos)
{
int m=strlen(t), n = strlen(s), i=pos, j=0, * nextval = new int[m];

get_nextval(t, nextval);

while(i<n && j<m)
{
if(j==-1 || s[i]==t[j])
{
++i;
++j;
}
else
{
j=nextval[j];
}
}

delete [] nextval;

if(j==m)
{
return s+i-m;
}
else
{
return NULL;
}

}

int main()
{
char s[] = "abcdefgh";
char t[] = "def";
char *p;

p= substr(s, t, 0);
if(p)
{
cout<<p<<endl;
}
else
{
cout<<t<<" is not a substring of "<<s<<endl;
}

p=substr_kmp(s, t, 0);
if(p)
{
cout<<p<<endl;
}
else
{
cout<<t<<" is not a substring of "<<s<<endl;
}

return 0;
}