最通俗易懂的KMP两种算法

KMP算法

1、概念

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

时间复杂度：O(m+n)

2、算法思路

一般在匹配2组字符串时，从头开始，一一对应，发现不对，又是从头开始一一对应，这样很好时，时间复杂度是：o(mn)。
这时KMP算法就很好的解决，因为它的时间复杂度：o(m+n)。
例子：

目标串：ababcabcbababcabacaba

模式串：ababcaba

先在模式串中获取 next 的临时数组。作用：用来帮组我们找到回退的次数。

有两种方法，来计算 next 临时数组。

以下两种方法计算的结果：

7.png

第一种：

按照以下3步循环操作：
1. next[i] = j;
2. i++;
3. 相同：j++;
   不同：j = next[j - 1];

代码

/**
 * @param dest
 * @return 临时数组
 */
public static int[] getKmpNext(String dest) {
    char[] pattern = dest.toCharArray();
    int[] next = new int[pattern.length];
    int j = 0;
    next[0] = j;
    for (int i = 1; i < pattern.length; i++) {// 2.i++
        while (j > 0 && pattern[i] != pattern[j]) {// 3.不同：j = next[j - 1];
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {// 3.相同：j++
            j++;
        }
        next[i] = j; // 1. next[i] = j
    }
    return next;
}

第二种：

借鉴：bilibili视频讲解

1. 相同：next[i] = j + 1;
        j++;
        i++;
2. 不同：if(j != 0)
            j = next[j - 1];
        else 
            ext[i] = 0;
            i++;

代码

/**
 * @param dest
 * @return 返回临时数组
 */
private static int[] kmpNext(String dest) {
    char[] pattern = dest.toCharArray();
    int[] next = new int[pattern.length];
    int j = 0;
    for (int i = 1; i < pattern.length; ) {
        if (pattern[i] == pattern[j]) {
            next[i] = j + 1;
            j++;
            i++;
        } else {
            if (j != 0) {
                j = next[j - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

3、完整代码

/**
 * author: bobo
 * create time: 2018/12/26 1:21 PM
 * email: jqbo84@163.com
 */
public class KMP {

    /**
     * @param dest
     * @return 返回临时数组
     */
    public static int[] getKmpNext(String dest) {
        char[] pattern = dest.toCharArray();
        int[] result = new int[pattern.length];
        int j = 0;
        result[0] = j;
        for (int i = 1; i < pattern.length; i++) {// 2.i++
            while (j > 0 && pattern[i] != pattern[j]) {// 3.不同：j = next[j - 1];
                j = result[j - 1];
            }
            if (pattern[i] == pattern[j]) {// 3.相同：j++
                j++;
            }
            result[i] = j; // 1. next[i] = j
        }
        return result;
    }

    /**
     * @param pattern
     * @return 返回临时数组
     */
    private static int[] kmpNext(char pattern[]) {
        int[] lps = new int[pattern.length];
        int index = 0;
        for (int i = 1; i < pattern.length; ) {
            if (pattern[i] == pattern[index]) {
                lps[i] = index + 1;
                index++;
                i++;
            } else {
                if (index != 0) {
                    index = lps[index - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

   /**
    * 查询子序列的匹配成功后，返回原字符串的位置
    * @param src
    * @param dest
    * @return 返回位置
    */
    public static int kmp(String src, String dest) {
        int[] next = getKmpNext(dest);
        char[] s1 = src.toCharArray();
        char[] s2 = dest.toCharArray();
        for (int i = 0, j = 0; i < s1.length; i++) {
            while (j > 0 && s1[i] != s2[j]) {
                j = next[j - 1];
            }
            if (s1[i] == s2[j]) {
                j++;
            }
            if (j == s2.length) {
                return i - j + 1;
            }
        }
        return 0;
    }
}

4、测试及结果

@Test
public void testKmp() {
    String dest = "ababcaba";

    int[] next = getKmpNext(dest);
    for (int i : next) {
        System.out.print(i + " ");
    }
    System.out.println();

    String src = "ababcabcbababcabacaba";
    int index = kmp(src, dest);
    System.out.println("index = " + index);
}

结果：

next: 0 0 1 2 0 1 2 3 
index = 9

最后编辑于：2019.03.19 19:05:37