////3.26日有感！
不管看多少博文，关于KMP，都不如花些时间去看严老师的讲解视频有效果，
上：http://v.youku.com/v_show/id_XODYxNjExODQ=.html 第 34分钟开始
下：http://www.56.com/u28/v_NjAwMzA0ODA.html
严蔚敏
虽然严老师讲话速度慢些，最开始会觉得不耐烦，甚至想快进什么的，但是对我而言，正因为脑袋不那么太灵光才会看那么多都不懂，严老师慢慢的讲解正好弥补了
我跟不上思路的毛病！简直完美！
目标字符串 T
模式字符串 P
朴素的匹配算法很好懂，就是先比较T和P的第一位如果不匹配就把P后移一位····
而KMP算法---的确如很多博客所言有点难理解诶，尝试过找个视频···不过http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
看完 仍觉得部分匹配表的部分不是很清晰，继续查
http://blog.csdn.net/itsenlin/article/details/21491787
理解了一下做此记录
模式P： A B C D A B D
部分匹配值：0 0 0 0 1 2 0
怎么得到的呢
是以第一个字符到当前字符 的前缀 和后缀 的最长的共有元素的长度
A：“A”的前缀null,后缀 null------没有共有元素-----长度=0
B: “AB”的前缀[A] 后缀[B]------没有共有元素----长度=0
C：“ABC”的前缀[A,AB]，后缀[BC,C]------没有共有元素------长度=0
D：“ABCD”的前缀[ABC,AB,A]，后缀[BCD,CD,D]------没有·····长度=0
A：“ABCDA”前缀[ABCD,ABC,AB,A],后缀[BCDA,CDA,DA,A]-----有共有元素了！A！所以最长共有元素长度！=1
B：“ABCDAB”前缀[ABCDA,ABCD,ABC,AB,A]后缀[BCDAB,CDAB,DAB,AB,B]---还有共有元素，只有一个 是AB 长度=2，所以最长的=2
D：“ABCDAB,ABCDA,ABCD,ABC,AB,A” [BCDABD,CDABD,BABD,ABD,BD,D]-----共有元素。。没有，所以=0
根据反证法【具体咋证明的我也没证····】
next[j+1]<=next[j]+1;
特别的，当且仅当p[j]=p[next[j]]时候，取等号 即 next[j+1]==next[j]+1
P模式串 P[0,j-1], (j), P[j,m]
P模式串P[0,next[j] ], (j+1), P[j+2,m]
*号代表配上的了，而
所以根据这一点就可以用递推，来计算next[]了
public int KMP(String P,String T) { int[] next=buildNext(P); int pLength=P.length(); int tLength=T.length(); int p=0,t=0;//作为类似指针的东西 while(t<tLength&&p<pLength) { if(p<0||P.charAt(p)==T.charAt(t)) { t++; p++; } else p=next[p]; } return t-p; }
public int[] buildNext(String p) { int j=0; int pLength=p.length(); int next[]=new int[p.length()]; int t=next[0]=-1; while(j<pLength-1) { if(0>t||p.charAt(j)==p.charAt(t))//匹配 { next[++j]=++t; } else t=next[t];///失配 } return next; }