数据结构关于串的KMP算法的理解高手请进

主要理解next[j]的含义即可，当然还有next函数的改进算法

KMP 算法是一种字符串的模式匹配算法，参看严蔚敏数据结构一书，里面讲的很清楚。
基本的字符串匹配算法是将被匹配的字符串S和模式串T 逐个字符进行比较。例如:S中有10个字符，T中有5个字符。S串初始的匹配位置为3.则从S中的第3个字符与T中的第一个字符匹配，若相同则S的第4个字符与T中的第2个字符匹配。直到匹配成功或者出现失配字符。当出现失配情况下，移动标识S中当前进行比较的字符指针，会退到第4个字符处。然后，重复这一过程。简单说，基本的字符匹配算法是通过移动被匹配的字符串S，进行比较字符的指针位置来完成字符匹配的。
而KMP算法刚好相反，在整个匹配过程中S中当前比较字符的指针并不发生回退现象，当出现S中的字符与T中的字符失配的时候。通过改变T的当前比较字符位置的指针来确定当前S中的字符该与T中哪个字符进行比较。简单说，通过模式字符串T的当前比较字符的指针的回退来完成字符匹配。
当理解了KMP算法通过改变T的当前比较字符位置的指针来完成匹配时，接下来要理清的是模式字符串T中的字符指针在失配的情况下是如何移动的。
以严蔚敏数据结构一书中KMP为例，对于模式字符串T，KMP维护了一个对应于T中每个字符弱发生失配情况下，指针回退到哪一位置的数组。当被匹配串S与模式串T发生失配的情况下，T读取数组中相应记录的位置，讲指针回退。如果回退后仍然失配则S的当前比较字符位置指针+1，T串指针回到第一个字符处。
由此可见获取数组中存储的数据是KMP算法的关键，书中的公式看起来有点抽象。数组中的存储指针的位置是根据，模式串T与自身的匹配过程获取的。
实际上是说，模式串T的第一个字符，如果出现失配则不会回退；当前比较位置的字符向前N-1位的子串恰好与T中从第一个字符起止N-1个字符形成的子串相等，且N小于当前位置，满足这些条件的N的最大值即为T当前位置指针回退的位置，然后迭代此过程，直到T本身匹配或回退到第一个字符位置仍不匹配，则当前位置的对应的回退位置指针指向T中的第一个字符所在位置。

讲的还不是很清楚，主要是对比一下基本的字符匹配算法和KMP的不同。一个是通过移动被匹配字符串比较字符的指针来实现匹配，一个是移动模式字符串的当前比较字符的位置指针来实现匹配。对于匹配串字符回退位置这个计算书中已经很清楚，根据算法单步调试一次自然就理解了。