基本介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

应用场景

有一个字符串str1 = "翻蹄亮掌=翻蹄亮掌一皮鞋",和一个子串str2 = "翻蹄亮掌一皮鞋",判断str1中是否有str2，如果有就返回第一次出现的下标，没有返回-1

暴力匹配算法

思路

现在str1匹配到的下标为i，str2匹配到的下标为j
1）如果当前字符匹配成功（str1[i] == str2[j]）,i++,j++
2）如果失败，就 i -= j + 1,j = 0
缺点：如果匹配失败，会移动到下一位接着判断，产生大量的回溯，浪费时间。

代码

public class ViolenceMatch {
  public static void main(String[] args) {
    String str1 = "翻蹄亮掌=翻蹄亮掌一皮鞋";
    String str2 = "翻蹄亮掌一皮鞋";
    int index = violenceMatch(str1, str2);
    System.out.println("index = " + index);
  }

  /**
   * 暴力匹配算法
   * @param str1 原字符串
   * @param str2 查找的字符串
   * @return 如果找到就返回第一次出现的下标，没有就返回-1
   */
  public static int violenceMatch(String str1,String str2) {
    char[] char1 = str1.toCharArray();
    char[] char2 = str2.toCharArray();
    int s1Length = char1.length;
    int s2Length = char2.length;
    int i = 0;
    int j = 0;
    while (i < s1Length && j < s2Length) {
      if (char1[i] == char2[j]) {
        i++;
        j++;
      } else {
        i = i - (j - 1);
        j = 0;
      }
    }
    if (j == s2Length) {
      return i - j;
    } else {
      return -1;
    }
  }

}

部分匹配表

现有字符串"java",它的前缀为：j,ja,jav,后缀：ava,va,a。
部分匹配值就是对于一个字符串而言它的前缀和后缀最长的相同元素的长度。以"ABCDABD"为例，
1）'A'的前缀和后缀为空，相同元素的长度为0。
2）'AB'的前缀为'A',后缀为'B',相同元素的长度为0。
3）'ABC'的前缀为'A'、'AB'，后缀为'BC'、'C',相同元素的长度为0。
4）'ABCD'的前缀为'A'、'AB'、'ABC',后缀为'BCD'、'CD'、'D',相同元素的长度为0。
4) 'ABCDA'前缀为'A'、'AB'、'ABC'、'ABCD',后缀为'BCDA'、'CDA'、'DA'、'A',相同元素的长度为1。...以此类推

KMP思路

现有字符串str1 = "ABAADCAAAAB",和一个子串str2 = "AAA",判断str1中是否有str2，如果有就返回第一次出现的下标，没有返回-1
i指向str1匹配字符的位置，j指向str2匹配字符的位置，当str1[i] != str2[j]时 并且j不等于0(前面的字符有相等的)，此时j -= (已经匹配的字符数 - 对应的部分匹配值)

代码

public class KMPAlgorithm {
  public static void main(String[] args) {
    String str1 = "ABAADCAAAAB";
    String str2 = "AAA";
    int[] next = kmpNext(str2);
    System.out.println("next = " + Arrays.toString(next));
    int index = kmpSearch(str1, str2, next);
    System.out.println("index = " + index);
  }

  /**
   * 返回字符串对应的部分匹配表
   * @param str 字符串
   * @return 字符串对应的部分匹配表
   */
  public static  int[] kmpNext(String str) {
    int[] next = new int[str.length()];
    for (int i = 1,j = 0; i < next.length; i++) {
      while (j > 0 && str.charAt(i) != str.charAt(j)) {
        j = next[j - 1];
      }
      if (str.charAt(i) == str.charAt(j)) {
        j++;
      }
      next[i] = j;
    }
    return next;
  }

  /**
   * kmp算法
   * @param str1 原字符串
   * @param str2 查找的字符串
   * @param next 查找的字符串对应的部分匹配表
   * @return 如果找到就返回第一次出现的下标，否则返回-1
   */
  public static int kmpSearch(String str1,String str2,int[] next) {
    for (int i = 1,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;
      }
    }
    return -1;
  }

}