请在深入理解KMP算法后阅读。–编者的话
当我第一次知道要做这个专题的时候，其实我是拒绝的..因为我根本不会，但是我加了特技！Duang！>_<
现在我们就来学习下基于KMP算法下的扩展KMP，首先我们这里所说的KMP不是拿来播放视频的某种软件（虽然本软件matrix67很喜欢【详情请见KMP算法详解】），假如你认为是那个播放软件的话你可以马上点击一下右上角的小叉..本文章不适合你。
首先我们在KMP算法中可以理解，next数组是KMP的核心，next[i]代表着以i为结尾和以开头为首的最长公共子串长度（也就是说对于st字符串数组的next[i]代表的就是st字符串数组从1开始到next[i]和从i-next[i]+1到i是完全相同的（st[1…next[i]]=st[i-next[i]+1…i]），不懂详见下图【图画的不好请见谅==】）
那么扩展KMP就高级了。一样还是next数组（还是原来的配方，还是熟悉的味道！），但是既然是扩展KMP就不要用next，我就改成extend数组了，表示的意义与普通KMP就大有不同。next[i]表示的是以i为首和以开头为首的最长前缀（也就是说对于st字符串数组中的next[i]表示的就是st字符串数组从1开始到extend[i]和从i到i+extend[i]-1是完全相同的（st[1…extend[i]]=st[i…i+extend[i]-1]），不懂的同样可以看下图【美术是语文老师教的..】）
我想各位看到这里已经基本理解了扩展KMP的基本要领了。同样，扩展KMP可以解决一系列的题目比如说最长回文子串、最长重复子串当然还有一些杂七杂八的字符串题目。和KMP一样，扩展的KMP同样需要我们在线性时间内求出extend数组，下面就给出求extend数组代码（本人是空格狂热者，为了出这个专题、照顾大家的感受，我毅然地拒绝了）以及证明过程（这个很难，我相信你们可以理解的）：
extend[1]=len;for(i=1;i<=len;i++){if(st[i]!=st[i+1])break;}extend[2]=i-1; k=2;int p,L;for(i=3;i<=len;i++){p=k+extend[k]-1; L=extend[i-k+1];if(p-k+1>i-k+L) extend[i]=L;//else if(p-k+1<i-k+L) extend[i]=_max(p-i+1,0);else{j=p-i+1;if(j<0) j=0;while(st[j+1]==st[i+j]&&i+j<=len) j++;extend[i]=j;k=i;}}
首先extend[1]就不用说了，直接等于len这个没有问题吧（假如有问题就撞墙死算了），那么因为extend[1]这个是具有一定性，所以我们基本把这东西废掉..那么我们就直接从extend[2]开始。然后我们就定义一个k，这个k表示的就是在当前搜索过的范围以内（因为这是线性算法，所以是从1到len）能到达最远（也就是说k+extend[k]+1最大的）的编号，为什么要定义一个这样子的东西，等下你们就知道了。
我们先定义一个p，让它等于k+extend[k]-1，那么由extend这个数组的定义我们就可以得到一个等式：st[1…extend[k]]=st[k…p]。因为p=k+extend[k]-1，所以我们又可以得到一条等式：extend[k]=p-k+1，把这个代换到上一条等式上，就会——瞬间爆炸！（好吧开个玩笑..）就会变成：st[1…p-k+1]=st[k…p]，如下图：
因为我们现在要求从extend[i]，那么由上面这条等式又可以得到另一条等式：st[i-k+1…p-k+1]=st[i…p]，如下图：
在看此证明过程中请各位一直记住extend数组所表达的含义，不然会有很多地方不懂的。那么我们再定义一个L=extend[i-k+1]，我们又可以得到一条等式：st[i-k+1…i-k+L]（注意：本来得到的应该是i-k+1+L-1，我直接把+1-1省略了）=st[1…L]，如下图：
这个时候有人就会问了：为什么你上面的图不和前几个合在一起呢？这个就是本算法的一个难点了！因为L的不定性，这个时候我们需要考虑i-k+L和p-k+1的大小！那我们就来分开来考虑。
（1）i-k+L<p-k+1，如下图：
从上图我们可以看到因为st[1…L]=st[i-k+1…i-k+L]，st[i-k+1…p-k+1]=st[i…p]，所以在st[i…p]中肯定含有一段（从i开始）和st[1…L]是完全相同的，也就是上图标出来的蓝色部分st[i…i+L-1]。因为st[i-k+1…p-k+1]=st[i…p]又因为i-k+L<p-k+1，所以我们又可以得到：st[i-k+L+1]=st[i+L]（也就是上图所标的黄色位置），而因为extend[i-k+1]的定义，所以st[L+1]（也就是上图所标棕色位置）!=st[i-k+L+1]，所以我们可以得到：st[i+L]!=st[L+1]，那么extend[i]就直接等于L了。
（2）i-k+L>p-k+1，如下图：
经历一种身体下了地狱，眼睛进入天堂，灵魂归入故里。
