书上原因说得很清楚,KMP对它的优化全放在T串在比较到不同时向前滑移,因为T串本身有前后相似的性质.所以对于T串比较小的时候,实际上没多大优化.

对于KMP算法其实不难理解,比较难理解的是求next[]值,实际上求next值是一个是自身对自身的匹配,可以比较一下求next的函数和KMP算法的函数.

就算你表面上理解了kmp算法，你也无法像学其他算法那样上升为直觉并举一反三的程度，因为这就是kmp，一个外星来的东东，算法世界里的金字塔（或百慕大）！*_*

#include <stdio.h>

void getnext (int next[], char *s)
{
    int i = 0, j = -1;

    next[0] = -1;
    while (s[i])
        if (j == -1 || s[i] == s[j]) {
            ++i; ++j;
            if (s[i] == s[j])
                next[i] = next[j];
            else
                next[i] = j;
        }
        else j = next[j];
}

int kmp (char *main, char *sub, int next[])
{
    int i, j, subn;

    subn = strlen (sub);
    for (j = i = 0; j < subn && main[i];) {
        if (j == -1 || main[i] == sub[j]) {
            i++; j++;
        }
        else j = next[j];
        /* printf ("i:%d j:%d\n", i, j);
        */
    }

    if (sub[j] == 0) return i - j;
    else return -1;
}

kmp真的有二楼说的那么难吗？我想一个算法肯定是有它的思想有它的内涵的，我知道了所以但是我更想知道所以然，不然这样也是表面的懂，不是真正意义上的理解，我想理解了才是记住的基础
 我们在上模式匹配这一节的内容的时候，老师讲的有些快，而且我觉得老师也有点讲不清楚，所以自己就对这一概念朦胧，顺便说一下我们用的教材是比较老的复旦大学出版社的《数据结构》是蔡子经和施伯乐编的，书上的程序真的很精练，而且有点难懂。
但是我还是要谢谢以上帮我的两位朋友，谢谢你们，希望你们看到我的帖子后，能给我继续讲讲！

还有个KMP算法的改进版,能求出所有匹配子串
求出next[j]后,再求出new next
假设 j  1  2  3  4  5
模式    a  b  a  c  a
next[j] 0  1  1  2  1
new     0  1  0  2  0