关于模式匹配算法，ＢＦ是比较号理解的，但是属于暴力匹配，资源浪费太严重。
KMP算法确实比较难懂（ＰＳ：反正我是看了好久才弄明白，可能也是我理解能力太差＝_＝）
下面是我的一些心得。
http://www.cnblogs.com/yjiyjige/p/3263858.html
这个是我在网上找到的一个网友的帖子，觉得将得很详细，看了之后恍然大悟。
1.原理
ＫＭＰ算法原理就是在主串和子串做匹配的时候，每次遇到不想同的元素即不能继续匹配时，保持主串正在匹配的那个元素不变，至变更子串的元素（向前移动游标），从而达到减小时间复杂度的目的。即：“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。”
结合这个帖子：http://www.cnblogs.com/tangzhengyue/p/4315393.html
我觉得最重要的是这个图要懂：
代码中，ＢＭＰ方法部分相比于ＢＦ算法改动不大，主要是在判断条件上加了一个
当si=tj时，i/j分别加１，继续比较；
当si!=tj时，i值不变，j变为next(j),继续比较。
做比较时有：１．j退回到next[j]时，若si=tj(tnext(j)),则i/j分别加１,继续比较，若si！=tj(tnext(j))，则j退回j=next[next[j]](即退回k=next[j],j=next[k],这是一个递归，直到k=-1,此时next[k]=0,k=1,next[k]=0)；
２．j退回到j=-1时，另主串和子串下标各加１．
分析条件，子串中的元素要进行比较的情况有：如上黄颜色标出的情况，进行综合得：
有代码：
int j=-1;
while(i<p.length&&j<s.length){
if(j==-1||p[i]==s[i]){
i++;j++}
else{
j=next[j];}}
关于j的变化关系由一个next数组来存储。
对整个子串进行遍历：（０<=j<s.length－１）得到next[]数组的个元素
int[] next1=new int[s.length];//next数组初始化
next1[0]=-1;//next数组的第一个元素初始化
int j=0;
int k=-1;//初始化
while(j<s.length-1)
{
if(k==-1||s[j]==s[k])//如果s[j]==s[k]或k==-1，则需要移动j,或则做单纯的做i++ j++,然后值j为０，子串从头开始
{
if(s[++j]==s[++k]){
next1[j]=next1[k];
}else{
System.out.println("j："+j);
System.out.println("k："+k);
next1[j]=k;
}
}else{//s[j]==s[k]和k==-1，都不满足，则往更深以层次比较next(k)
//此时s[j]！=s[k]
k=next1[k];//取k结束的串的最长匹配子串
}
总代码：
package exercise;
import java.util.Scanner;
public class KMP {//与ＢＦ算法有四个不同的地方
public static int km(String s1,String s2){
char[] p=s1.toCharArray();
char[] s=s2.toCharArray();
int[] next=getnext(s2);//与ＢＦ算法相比多了一个next[]数组 １
for(int l=0;l<next.length;l++){
System.out.print(next[l]+" ");
}
int i=0;//主串
int j=0;//子串
while(i<p.length&&j<s.length){
if(j==-1||p[i]==s[j]){//j==-1是当主串和子串的第一个元素不等时 多了一个j的判断条件 ２
i++;
j++;
}else{
//与ＢＦ算法不同的是，此时i不在返回，只有j动 //ｉ不动 3
j=next[j];//j回到指定位置
//j不是移动到０，而智能的移动到字串中的最长匹配串的结束位置+1 4
}
}//while结束
if(j==s.length){//s.length
return i-j;
}else{
return -1;
}
}
public static int[] getnext(String s2){
char[] s=s2.toCharArray();//将要个生成next数组的子串转换为char数组
int[] next1=new int[s.length];//next数组初始化
next1[0]=-1;//next数组的第一个元素初始化
int j=0;
int k=-1;//初始化
while(j<s.length-1)
{
if(k==-1||s[j]==s[k])//如果s[j]==s[k]或k==-1，则需要移动j,或则做单纯的做i++ j++,然后值j为０，子串从头开始
{
if(s[++j]==s[++k]){
next1[j]=next1[k];
}else{
System.out.println("j："+j);
System.out.println("k："+k);
next1[j]=k;
}
}else{//s[j]==s[k]和k==-1，都不满足，则往更深以层次比较next(k)
//此时s[j]！=s[k]
k=next1[k];//取k结束的串的最长匹配子串
}
}
return next1;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
System.out.println("请输入主串：");
String p=sc.nextLine();
System.out.println("请输入子串：");
String s=sc.nextLine();
int i=km(p,s);//静态的方法main()只能调用静态的方法b(),因为静态方法早于对象而创建，
//调用非静态方法时要提前创建对象，非静态方法要等对象创建之后才能被创建
System.out.println("子串在主串中的位置："+i);
}
}结果：
请输入主串：
ababcabdabcabca
请输入子串：
abcabc
j：1
k：0
j：2
k：0
-1 0 0 -1 0 0 子串在主串中的位置：8