KMP算法之深入浅出
凡是数据结构的课本上都会有讲解串的一节，那么必然会讲解串的模式匹配，在进行文本编辑时，我们时常进行查找和替换，这就是串的模式匹配的一种应用，下面讲解两种模式匹配算法：Brute-Force和KMP算法
Brute-force算法：
设目标串：target="ababdabcd"
模式串："abc"
匹配过程：
如图：匹配过程就是将pattern和target字符串一个个的比较，当遇到某一个字符不等的时候，pattern回溯到字符串最前端，target回溯到开始比较的下一个位置，如图2,当第一次匹配失败后，target是从第二个字符开始的。
具体代码如下：
//使用Brute-force算法进行串的模式匹配public int indexof1(String target,String pattern){int i=0;int j=0;//如果pattern为空或者其长度大于target，那么不用比较if(pattern.length()>target.length()||pattern==null){return -1;}while(j<pattern.length() && i<target.length()){if(target.charAt(i)==pattern.charAt(j)){i++;j++;}else{i=i-j+1;j=0;}}if(j==pattern.length()){System.out.println("i="+i+"j="+j);return i-j;}return -1;}
KMP算法：
kmp算法是对Brute-Force的一种改进，在上面的算法中，每次匹配失败后，target都要回溯到开始比较的下一个位置，pattern要回溯到字符串的开始，由于很多比较在上一次（失败的一次）已经进行过，所以很多比较是没有必要的。
如：target ="aacaababcefg"
pattern="aab"
如果按照上面的算法，当比较第三个字符时，匹配失败了，target要移动到第二个字符开始比较，pattern要移动到串头，不断匹配，只到完成
在介绍KMP算法之前，先说明一个问题：
“abcab” 该字符串的左子串和右子串的最大长度是2
“ab” 该字符串的左子串和右子串的最大长度是0
"aba" 该字符串的左子串和右子串的最大长度是1
明白这点事明白kMP算法的关键：
在kmp算法中，要对pattern字符串生成 一个next[]数组，其长度和pattern的字符数相同，next[j]表示0到j-1字符串的左子串和右子串的最大长度
下面给出获得next数组的方法：
public int[] getNext(String pattern){int[]next=new int[pattern.length()];next[0]=-1;int j=0;int k=-1;while(j<pattern.length()-1){if(k==-1 ||pattern.charAt(j)==pattern.charAt(k)){j++;k++;next[j]=k;}else{k=next[k];}}return next;}
KMP算法：
//使用KMP算法进行串的模式匹配public int indexof2(String target,String pattern){int []next=this.getNext(pattern);System.out.println(Arrays.toString(next));int i=0;int j=0;//如果pattern为空或者其长度大于target，那么不用比较if(pattern.length()>target.length()||pattern==null){return -1;}while(j<pattern.length() && i<target.length()){if(j==-1||target.charAt(i)==pattern.charAt(j)){i++;j++;}else{j=next[j];}}if(j==pattern.length()){return i-j;}return -1;}