字符串匹配之KMP算法思路、原理与Java实现

问题描述：

判断字符串a是否包含字符串b。我们称a为文本串，b为模式串。比如

a = bcabcabcabbcabcabcabcabd
    ||||||||||/
b = bcabcabcabc

算法思路：

如上例中/处两个字符匹配失败，如果模式串右移一个字符从文本串第二个字符开始重新进行匹配，显然效率太低。

KMP算法的精髓在于当文本串和模式串发生不匹配时，利用模式串自身的特点，尽可能多的移动模式串，使之能够在文本串不匹配处继续进行匹配。

如上例，发生不匹配时，模式串可以右移三次，在目标串不匹配处继续进行：

a=bcabcabcabbcabcabcabcabd
     |||||||/
b=   bcabcabcabc

算法原理：

模式串b=b₁b₂b₃b₄…b_n,如果有b₁b₂b₃b₄…b_k-1等于b_j-(k-1)b_j-(k-2)b_j-(k-3)…b_j-1，那么在进行匹配时，如果在j处与文本串i处匹配失败，我们可以将模式串右移j-k个字符，即直接将文本串i处字符与b_k进行匹配。由于b₁b₂b₃b₄…b_k-1等于b_j-(k-1)b_j-(k-2)b_j-(k-3)…b_j-1，显然模式串前k-1位的字符是与文本串i处前k-1位字符是匹配的。

所以问题转化为求模式串各字符的k值，我们记作K(j)，该值可以根据模式串自身求得。

伪代码：

假设有文本串a和模式串b。index从1开始。

求K(j)的伪代码如下：

 

初始化：i = 1，j = 0, K(1) = 0；
while (i < b.length) {
   if (j == 0 || b(i) = b(j)) {
       i++;
       j++;
       K(i) = j;
   } else {
       j = K(j);
   }
}

判断匹配的伪代码如下：

 

初始化：i = 1, j = 1；
while (i <= a.length && j <= b.length) {
    if (j ==0 || a(i)= b(j)) {
             i++;
             j++;
    } else {
             j = K(j);
    }
}
if (j > b.length) {
    return true;
}
return false;

 

Java实现：

package cn.dfeng;

/**
 * KMP算法的实现
 * @author dfeng
 *
 */
public class KMPAlgorithm {

    /**
     * 判断是否匹配
     * @param target 目标文本串
     * @param mode 模式串
     * @return 匹配结果
     */
    public static boolean matchString(String target, String mode) {
        //为了和算法保持一致，使index从1开始，增加一前缀
        String newTarget = "x" + target;
        String newMode = 'x' + mode;

        int[] K = calculateK(mode);

        int i = 1;
        int j = 1;
        while(i <= target.length() && j <= mode.length()) {
            if (j == 0 || newTarget.charAt(i) == newMode.charAt(j)) {
                i++;
                j++;
            } else {
                j = K[j];
            }
        }

        if (j > mode.length()) {
            return true;
        }
        return false;
    }

    /*
     * 计算K值
     */
    private static int[] calculateK(String mode) {
        //为了和算法保持一致，使index从1开始，增加一前缀
        String newMode = "x" + mode;
        int[] K = new int[newMode.length()];
        int i = 1;
        K[1] = 0;
        int j = 0;

        while(i < mode.length()) {
            if (j == 0 || newMode.charAt(i) == newMode.charAt(j)){
                i++;
                j++;
                K[i] = j;
            } else {
                j = K[j];
            }
        }

        return K;
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        String a = "bcabcabcabbcabcabcabcab";
        String b = "bcabcabcabc";//"ababbaaba";//
        System.out.println(KMPAlgorithm.matchString(a, b));

    }

}