KMP匹配算法代码实现

有需要可以看看，下面是一个测试，（笔记）

package 十大算法;
import java.util.Arrays;
public class KMP {
public static void main(String[] args) {
 String str1="bbc abcdab abcdabcdabde";
 String str2="abcdabd";
 int[]next=kmpnext("abcdabd");
 int index=kmpsearch(str1, str2, next);
 System.out.println(index);
}
//kmp搜索算法
/**
 * 
 * @param str1 源字符串
 * @param str2 字串
 * @param next 部分匹配表，是字串对应的部分匹配表
 * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
 */
public static int kmpsearch(String str1,String str2,int []next) {
 for(int i=0,j=0;i<str1.length();i++) {
  //当str1.charAt(i)!=str2.charAt(j),去调整j的大小
  //移动位数=已匹配的字符数-对应的部分匹配值
  while(j>0 && str1.charAt(i)!=str2.charAt(j)) {
   j=next[j-1];
  }
  if(str1.charAt(i)==str2.charAt(j)) {
   j++;
  }
  if(j==str2.length()) {
   //找到
   return i-j+1;
  }
 }
 return -1;
}
//获取到一个字符串（字串）的部分匹配值表
public static int[]kmpnext(String dest){
 //创建一个next数组保存部分匹配值
 int []next=new int[dest.length()];
 next[0]=0;//如果字符串的长度为1，部分匹配值就是0
 for(int i=1,j=0;i<dest.length();i++) {
  //当dest.charAt(i)!=dest.charAt(j),需要从next[j-1]获取新的j
  //直到发现有dest.charAt(i)==dest.charAt(j)成立才退出
  while(j>0&&dest.charAt(i)!=dest.charAt(j)) {
   j=next[j-1];
  }
  //当dest.charAt(i)==dest.charAt(j)满足时，部分匹配值就是+1
  if(dest.charAt(i)==dest.charAt(j)) {
   j++;
  }
  next[i]=j;
 }
 return next;
}
}

目前我看到讲的比较好理解的视频是这两个，
https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=3885756804092911843
https://www.bilibili.com/video/BV1Px411z7Yo?from=search&seid=3885756804092911843