KMP算法

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。

解决上述问题的直观方法是使用暴力匹配方法，即从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。

初始化：

之后比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动

A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤

这个方法的缺点是效率太低，无法利用之前部分匹配的有效信息。

KMP算法的思想是：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置。

如上图，当C、D不匹配，我们保持i指针不动，使j指向模式串的1位置，这样就可以略过很多已经检查过的比较，提高匹配效率。

当i，j指针指向元素不匹配时，如果确定j指针接下来指向哪，这个问题由以下函数解决，我们定义一个next数组保存j指针不匹配时指向哪里。

public static int[] getNext(String ps) {

    char[] p = ps.toCharArray();

    int[] next = new int[p.length];

    next[0] = -1;

    int j = 0;

    int k = -1;

    while (j < p.length - 1) {

       if (k == -1 || p[j] == p[k]) {

           next[++j] = ++k;

       } else {

           k = next[k];

       }

    }

    return next;

}

 

接下来，我们就可以使用KMP算法求解子串匹配问题了。

public static int KMP(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    int[] next = getNext(ps);

    while (i < t.length && j < p.length) {

       if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0

           i++;

           j++;

       } else {

           // i不需要回溯了

           // i = i - j + 1;

           j = next[j]; // j回到指定位置

       }

    }

    if (j == p.length) {

       return i - j;

    } else {

       return -1;

    }

}

最后，来看一下上边的算法存在的缺陷。来看第一个例子：

上面子串的next数组应该是[ -1，0，0，1 ]，所以下一步我们应该是把j移动到第1个元素

但比较这个B是没有意义的，因为后面的B已经不匹配了，那前面的B也一定是不匹配的，为此，对next函数做如下优化：

public static int[] getNext(String ps) {

    char[] p = ps.toCharArray();

    int[] next = new int[p.length];

    next[0] = -1;

    int j = 0;

    int k = -1;

    while (j < p.length - 1) {

       if (k == -1 || p[j] == p[k]) {

           if (p[++j] == p[++k]) { // 当两个字符相等时要跳过

              next[j] = next[k];

           } else {

              next[j] = k;

           }

       } else {

           k = next[k];

       }

    }

    return next;

}