给定字符串A"abcaabcabb",模式串B"abcab"。求模式串第一次出现在给定字符串中的索引，如果没有则直接返回-1。
正常的解决方案是令i指向A中第一个元素，将A中元素一个一个和B中元素比较，如果不相等，则i++,重头再和B中元素比较。这一方案的时间复杂度为O(M*N)，效率是较低的。
KMP算法是解决字符串匹配问题的一个较优方案，算法思想如下。
首先将A中元素和B中元素比较
当匹配到A中的b与B中的a不相同时，我们并不急着令i++再从头比较。这里有一个基本信息时从i所指向的a一直到b的前一个元素d。A中"abca"这一段字符串和B的前缀是相同的。
因此实际上不需要i++我们也已经知道了i的下一个元素就是"b"，而且我们也可以提前知道"b"和B中的第一个元素"a"是不等的。因此对于A来说"b"是可以跳过的，我们只需要在"abca"中找到一个后缀和前缀相同就可以了，这句话有点绕，其实就好比字符串"abca"最长的相同前缀和后缀是"a"，那么i直接跳到这个a就可以了，而且此时我们知道B的第一个字符"a"是不需要比较的（因为必然和i指向的相同）
KMP算法会提前算好模式串B中所有字符相对于前缀的值next[i]。
设模式串为needle,得出next[]的代码如下:
//计算模式串的相关最长相同前缀
int[] next = new int[needle.length()];
next[0] = 0;
int a=1,b=0; //b表示前缀中每一个元素位置
for(;a<needle.length();++a){
if(needle.charAt(a)==needle.charAt(b)){
next[a] = b+1;
b++;
}else{
if(needle.charAt(a)==needle.charAt(0)){
next[a] = 1;
b = 1;
}else{
next[a] = 0;
b = 0;
}
}
}有了next[]之后每当我们匹配时发现不符时没有必要进行i++，可以对i进行回溯i +=j-next[j-1];（j指向不匹配的那个字符），这样就可以省去许多无用的循环匹配。
boolean flag = false;
int i=0;
int j=0;
while(i<haystack.length()&&j<needle.length()){
if(haystack.charAt(i+j)==needle.charAt(j)){
flag = true;
j++;
if(j<needle.length()&&i+j>=haystack.length()){
flag = false;
break;
}
}else{//前面有j个元素相等,进行回溯
flag = false;
if(j==0){ //如果第一个元素就不相同
i++;
}else{
i +=j-next[j-1];
j =next[j-1];
}
}
}
if(flag){
return i;
}
return -1;