KMP 算法理解

发表于： 分类于：
字数：2389 阅读：≈ 5分钟 浏览：

字符串前缀 与字符串后缀

  • 字符串前缀(Proper prefix) ：包含第一个字符，不包含最后一个字符的所有子串 例如：abababca 的前缀：a、ab、aba、abab、ababa、ababab、abababc

  • 字符串后缀(Proper suffix)：不包含第一个字符，包含最后一个字符的所有子串 例如：abababca 的后缀：a、ca、bca、abca、babca、ababca、bababca

字符串部分匹配表

字符串部分匹配表 (Partial Match Table) 也称为 next 数组，例如：abababca 的部分匹配表为：

charabababca
index01234567
value00123401

每列 value 值表示前 index + 1 个字符子串的最大字符串前缀与字符串后缀相匹配的长度，例如：

  • index 为 0 的子串为 a，没有字符串前缀和字符串后缀，所以 value 为 0
  • index 为 1 的子串为 ab，字符串前缀为 a，字符串后缀为 b，没有相匹配的字符串前缀与字符串后缀，所以 value 为 0
  • index 为 2 的子串为 aba，字符串前缀为 a、ab，字符串后缀为 a、ba，字符串前缀与字符串后缀相匹配的子串为 a，长度为 1，所以 value 为 1
  • index 为 3 的子串为 abab，字符串前缀为 a、ab、aba，字符串后缀为 b、ab、bab，字符串前缀与字符串后缀相匹配的子串为 ab，长度 2，所以 value 为 2
  • index 为 4 的子串为 ababa，字符串前缀为 a、ab、aba、abab，字符串后缀为 a、ba、aba、baba，字符串前缀与字符串后缀相匹配的子串为 a、aba，长度最大的为 aba ，所以 value 为 3
  • …
  • index 为 7 的子串为 abababca，字符串前缀为 a、ab、aba、abab、ababa、ababab、abababc，字符串后缀为 a、ca、bca、abca、babca、ababca、bababca，字符串前缀与字符串后缀相匹配的子串为 a，所以 value 为 1

KMP 算法思路

KMP 算法就是利用字符串部分匹配表可以计算出当模式串与主串不匹配时，模式串可以多后移几位 (默认后移 1 位)

当模式串与主串不匹配时，如果不匹配字符对应模式串下标大于 0 (非首个模式串字符)，取此字符前一个字符对应字符串部分匹配表中的 value ，如果 value 大于 0，模式串中不匹配字符之前 (不含不匹配字符) 子串长度减去 value 即模式串为后移的位数。

暴力匹配算法当模式串和主串不匹配时，主串匹配下标 +1，模式串匹配下标置为 0，KMP 算法优化点在于模式串匹配下标置为 value。

例如在主串 bacbababaabcbab 中查找模式串 abababca

  • 第一次符合以上规则的情况如下，模式串与主串不匹配字符 (b) 前一个字符为 a，对应字符串部分匹配表 index 为 0，value 为 0，所以不存在多后移情况
bacbababaabcbab
  |
 abababca
  • 第二次符合以上规则的情况如下
bacbababaabcbab
         |
    abababca
  • 模式串与主串不匹配字符 (b) 前一个字符是 a，对应字符串部分匹配表 index 为 4，value 为 3，不匹配字符之前模式串为 ababa 长度为 5， 所以后移 5-3=2 位
bacbababaabcbab
         |
      abababca
  • 模式串与主串不匹配字符 (b) 前一个字符是 a，对应字符串部分匹配表 index 为 2，value 为 1，不匹配字符之前模式串为 aba 长度为 3， 所以后移 3-1=2 位
bacbababaabcbab
           |
         abababca
  • 此时，模式串长度已经比剩余主串长，匹配结束。

代码实现

next 数组的代码实现思路参考 KMP 算法的 Next 数组详解

Golang 暴力匹配代码实现


// 暴力匹配
func Bf(s, p string) int {
    n := len(s)
    m := len(p)
    if n < m {
        return -1
    }

    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m {
            // 如果主串与模式串不匹配，则主串向右移动一个字符,模式串从头开始匹配
            if s[i+j] != p[j] {
                break
            }
            j++
        }
        if j == m {
            return i
        }
    }

    return -1
}

Golang KMP 代码实现

func Kmp(s, p string) int {
    n := len(s)
    m := len(p)
    if n < m {
        return -1
    }
    next := GetNext(p)

    for i := 0; i <= n-m; i++ {
        j := 0
        for j < m {
            // 暴力匹配算法当模式串和主串不匹配时，主串匹配下标 +1，模式串匹配下标置为 0，
            // KMP 算法优化点在于将模式串下标置为不匹配字符前一个字符对应 next 数组的值
            if s[i+j] != p[j] {
                // 当模式串与主串不匹配时，如果不匹配字符对应模式串下标大于 j > 0 (非首个模式串字符)，
                // 并且此字符前一个字符对应字符串部分匹配表中的值 next[j - 1] 也大于 0，
                // j - next[j - 1] 即模式串为后移的位数，等价于 j 置为 next[j - 1]

                if j != 0 && next[j-1] != 0 {
                    // j 后移 j-next[j-1]，等价于 j = next[j-1]
                    j = next[j-1]
                } else {
                    break
                }
            }
            j++
        }
        if j == m {
            return i
        }
    }

    return -1
}

func GetNext(p string) []int {
    n := len(p)
    next := make([]int, n)
    next[0] = 0
    k := 0

    // 根据已知 next 数组的前 i-1 位推测第 i 位
    for i := 1; i < n; i++ {
        for k > 0 && p[k] != p[i] {
            // k 为 p[0, i) 子串最大匹配前后缀长度
            // p[0, k) 为 p[0, i) 子串最大匹配前缀子串

            // 若：1、p[k] != p[i]，则求 p[0, i] 子串最大匹配前后缀长度问题
            // 转换成了求 p[0, k) 子串最大匹配前后缀长度问题
            // 循环直到 p[k] == p[i] (下一步处理) 或 k == 0
            k = next[k]
        }

        // 若：2、p[k] == p[i]，则 p[0, i] 子串最大匹配前后缀长度为 k + 1
        if p[k] == p[i] {
            k++
        }

        next[i] = k
    }
    return next
}

Java KMP 代码实现

package io.github.ehlxr.algorithm.match;

import java.util.Arrays;

/**
 * 字符串匹配算法 KPM
 *
 * @author ehlxr
 * @since 2022-03-13 10:06.
 */
public class Kmp {
    public static void main(String[] args) {
        String s = "bacbababaabcbab";
        String p = "abab";

        System.out.println(Arrays.toString(getNexts(p)));
        System.out.println(kmp(s, p));
    }

    public static int kmp(String s, String p) {
        char[] scs = s.toCharArray();
        char[] pcs = p.toCharArray();

        int m = s.length();
        int n = p.length();

        int[] next = getNexts(p);

        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (scs[i + j] != pcs[j]) {
                    // 暴力匹配算法当模式串和主串不匹配时，主串匹配下标 +1，模式串匹配下标置为 0，
                    // KMP 算法优化点在于将模式串下标置为不匹配字符前一个字符对应 next 数组的值
                    if (j > 0 && next[j - 1] > 0) {
                        // 当模式串与主串不匹配时，如果**不匹配字符**对应模式串下标大于 j > 0 (非首个模式串字符)，
                        // 并且此字符前一个字符对应字符串部分匹配表中的值 next[j - 1] 也大于 0，
                        // j - next[j - 1] 即模式串为后移的位数，等价于 j 置为 next[j - 1]
                        j = next[j - 1];
                    } else {
                        break;
                    }
                }
            }
            if (j == n) {
                return i;
            }
        }

        return -1;
    }

    private static int[] getNexts(String p) {
        int m = p.length();
        char[] b = p.toCharArray();
        int[] next = new int[m];

        next[0] = 0;
        int k = 0; // 表示前后缀相匹配的最大长度

        // 根据已知 next 数组的前 i-1 位推测第 i 位
        for (int i = 1; i < m; ++i) {
            while (k != 0 && b[k] != b[i]) {
                // k 为 b[0, i) 子串最大匹配前后缀长度
                // b[0, k) 为 b[0, i) 子串最大匹配前缀子串

                // 若：1、b[k] != b[i]，则求 b[0, i] 子串最大匹配前后缀长度问题
                // 转换成了求 b[0, k) 子串最大匹配前后缀长度问题
                // 循环直到 b[k] == b[i] (下一步处理) 或 k == 0
                k = next[k];
            }
            // 若：2、b[k] == b[i]，则 b[0, i] 子串最大匹配前后缀长度为 k + 1
            if (b[k] == b[i]) {
                ++k;
            }
            next[i] = k;
        }
        return next;
    }
}

参考 The Knuth-Morris-Pratt Algorithm in my own words