2. KMP算法

1. 部分匹配值表

解析： A=1, 是因为从A开始，只有1个字符和前面重复；——》前后缀重复字符的长度
B=2, 是因为有连续2个字符所组成的字符串重复

package MeituanTest;
public class Main2 {
  public static void main(String[] args) {
    String str1 = "BBC ABCDAB ABCDABCDABDE";
    String subStr = "ABCDABD";
  }
  /**
   * 写出KMP搜索算法
   *
   * @param str1 原字符串
   * @param str2 字串
   * @param next 字串的部分匹配表
   * @return -1就是没有匹配到，否则就是第一个下标
   */
  public static int kmpSearch(String str1, String str2, int[] next) {
    // i: str1的下标， j: str2的下标
    for (int i = 0, j = 0; i < str1.length(); i++) {
      // 当二者不相等时
      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;
      }
    }
  }
  // 获取字串的部分匹配值表
  public static int[] kmpNext(String dest) {
    // 因为需要拿到部分匹配值，所以要创建一个和字符串相同长度的数组
    int[] next = new int[dest.length()];
    //        在进行部分匹配值计算时，单个元素的字符串的字符永远对应值是0
    next[0] = 0;
    //        通用的情况，如果{abcdab}，则第2次出现的a和b的匹配值都是1，第一次的a和b的匹配值仍为0
    // 注意，这里的匹配是从头开始计算的，不是中间部分，比如： {1,2,3,a,4,5,6,a,7,8,9}, 从第2位开始遍历，每个元素都与首字符比较，不能跨过首字符
    // 当有相同的字符时，长度j+1， 下标i也+1开始后续继续匹配
    for (int i = 1, j = 0; i < dest.length(); i++) {
      while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
        j = next[j - 1]; // 如果不想等，则代表局部匹配值表中，对应的相同sub字符串的长度不再+1
      }
      // i位和j位匹配，则部分匹配值+1
      if (dest.charAt(i) == dest.charAt(j)) {
        j++;
      }
      // 后面的字符的匹配值才会增加，前面的不会
      next[i] = j;
    }
    return next;
  }
}