KMP算法(Java版)

KMP算法(Java版)

谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。

问题：

有一个文本串S，和一个模式串P，现在要查找P在S中的位置

0x01 暴力算法

// 暴力查找法：不一致的时候直接把i 移动到 i+1 的位置继续比较
private static int search(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();
  int i = 0, j = 0;
  while (i < sLen && j < pLen) {
    if (s.charAt(i) == p.charAt(j)) {
      // 字符相同，则继续匹配下一个字符
      i++;
      j++;
    } else {
      //  i，j 复位
      i = i - j + 1;
      j = 0;
    }
  }
  if (j == pLen) return i - j;
  return -1;
}

0x02 KMP算法

// KMP 查找法
private static int kmpSearch(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();
  int[] next = getNext(p);
  int i = 0, j = 0;
  while (i < sLen && j < pLen) {
    if (j == -1 || (s.charAt(i) == p.charAt(j))) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  if (j == pLen) return i - j;
  return -1;
}

// 计算next数组
private static int[] getNext(String p) {
  int len = p.length();
  int[] next = new int[len];
  next[0] = -1;
  int j = -1, i = 0;
  while (i < len - 1) {
    if (j == -1 || p.charAt(j) == p.charAt(i)) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  //        System.out.println(Arrays.toString(next));
  return next;
}