给个代码,代码本身简单,是背诵的佳品啊,知道了这些操作再对对解释吧

#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;
}

[此贴子已经被作者于2006-7-14 15:07:32编辑过]

啊，不好意思，因为没看过这本书，所以不敢妄加评论。
一本好的书，首先它会很容易让你看懂，其次它会很容易让你记住看过的内容，最后看它会让你心情愉快。
似乎太理想化了点，国内的书好象没有几本符合这些条件的。
这么说 吧，如果一本书讲的很有条理，很严密，一环扣一环，语言清晰，由浅入深，举例简单易懂并有很强的代表性，注释详细，那么这本书就很不错了

在这个例子之前，我专门写了一段话来针对这个问题

在解决这个问题的同时，我们又发现了一个问题，当这个子串为a b c d a f 时又会如何呢？因为无法判断主串中与a匹配对应的位置开始往后的部分是否与整个子串相匹配，所以子串最多向右移动4位，即a移动到a的位置上，然后再进行判断。

可能是排版太密了，容易让人忽视这段话

子串 a b a b a a b a b
next[j] 0 1 1 2 3 4 2 3 4

下面的一排数字是对应的next[j] 值， 是通过子串求出来的 ， 子串中每个字符对应一个next[j] 值，隔开些可能更清楚，顺便用颜色漂了下

对于next[j]的作用请看这里

子串 a b a b a a b a b
next[j] 0 1 1 2 3 4 2 3 4
匹配子串长度 1 2 3 4 5 6 7 8 9 （对应位置 也可看成是截止到当前字符的子串串长）
最大右移 1 1 2 2 2 2 5 5 5 （当前字符不匹配时，子串最大右移距离）

我们发现，最大右移 + 对应的next[j] = 匹配子串长度，我估计这就是为什么要引入next[ j ] 这个参量，为了方便计算最大右移。

[此贴子已经被作者于2006-7-14 15:55:04编辑过]

KMP算法的核心内容就是计算子串的最大右右移位数，只要找到方法求出子串的最大右移位数，问题就基本解决了，而子串的最大右移位数本身没有规律，因此引入了有规律的next[j] 这个参量，来达到方便计算最大右移位数的目的。

  精华啊 精华 谢斑竹了 小弟更加的懂了 同时也谢谢11楼的

小弟初学数据结构 思维能力不是太发达 所以希望大家多多帮助啊

斑竹 其实我觉得你应该出本书保证比那些所谓的什么清华的要好，他们的我看了N边 不明白，看了你的几边 就明白了

[此贴子已经被作者于2006-8-8 15:55:42编辑过]

next[1]=0,
设next[j]=k,
next[j+1]=?有两种可能：
（1）若p(k)=P(j),即next[j+1]=k+1；则next[j+1]=next[j]+1;
(2)若p(k)！=p(j)：
将模式向右滑动至以模式中的第next[k]个字符和主串中的第j个字符相比较。若next[k]=k'，且p（i）=p（k’），则说明在主串中第j+1个字符之前存在一个长度为k’（即next[k]）的最长子串，和模式串中从首字符起长度为k’的子串相等，即next[j+1]=k’+1；即next[j+1]=next[k]+1；
同理：若p（j）！=p（k’），则将模式继续向右滑动至将模式中第next[k’]个字符和p（j）对齐，........依次类推，直至p（j）和模式中某个字符匹配成功或者不存在任何k’（1 <k'<j)满足匹配，则next[j+1]=1。

讲的真是太棒了，
比书上好懂多了！
厉害！！！