[一文说透] KMP 字符串匹配算法

作者: 蓝笔头 | 来源:发表于2021-08-20 08:52 被阅读0次

leetcode 题目：28. 实现 strStr()

1. BF 算法（Brute Force）

暴力枚举每一个 text 下标 textIndex，从 textIndex 进行匹配。

双指针

textIndex：指向文本串的当前位置
patternIndex：指向模式串的当前位置

    public int indexOf(String text, String pattern) {
        // 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
        if (pattern.equals("")) {
            return 0;
        }

        // 因为匹配成功时，匹配的串长度和 pattern 串的长度一样
        // 又因为 textIndex 表示匹配串的开始下标

        // 因此如下等式：
        // textIndex + pattern.length() <= text.length();

        // 转换一下公式可以得到：
        // textIndex <= text.length() - pattern.length();
        int maxTextIndex = text.length() - pattern.length();

        for (int i = 0; i <= maxTextIndex; ++ i) {
            if (match(text, pattern, i)) {
                return i;
            }
        }

        return -1;
    }

    // 从 textIndex 开始匹配
    public boolean match(String text, String pattern, int textIndex) {
        for (int i = 0; i < pattern.length(); ++ i) {
            boolean match = text.charAt(textIndex + i) == pattern.charAt(i);
            if (!match) {
                return false;
            }
        }

        // 全部匹配成功
        return true;
    }

最坏的时间复杂度：O(n * m)，n 为 text 的长度，m 为 pattern 的长度。

打印匹配过程：

public class BFDemo {
    public static void main(String[] args) {
        String text = "ABABACAB";
        String pattern = "ABACA";
        int i = indexOf(text, pattern);
        System.out.println("index = " + i);
    }

    public static int indexOf(String text, String pattern) {
        // 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
        if (pattern.equals("")) {
            return 0;
        }

        // 因为匹配成功时，匹配的串长度和 pattern 串的长度一样
        // 又因为 textIndex 表示匹配串的开始下标

        // 因此如下等式：
        // textIndex + pattern.length() <= text.length();

        // 转换一下公式可以得到：
        // textIndex <= text.length() - pattern.length();
        int maxTextIndex = text.length() - pattern.length();

        for (int i = 0; i <= maxTextIndex; ++ i) {
            if (match(text, pattern, i)) {
                return i;
            }
        }

        return -1;
    }

    // 从 textIndex 开始匹配
    public static boolean match(String text, String pattern, int textIndex) {
        int delimiterLength = 40;
        printDelimiter('=', delimiterLength, true);
        System.out.println(String.format("第 %d 次匹配", textIndex + 1));
        printDelimiter('=', delimiterLength, true);

        for (int i = 0; i < pattern.length(); ++ i) {
            boolean match = text.charAt(textIndex + i) == pattern.charAt(i);

            // 打印匹配过程
            System.out.println(getMatchText(text, textIndex + i));
            printDelimiter(' ', textIndex, false);
            System.out.println(getMatchText(pattern, i));
            System.out.println(String.format("textIndex = %d, patternIndex = %d, 当前字符匹配结果：%s", textIndex + i, i, match));

            printDelimiter('-', delimiterLength, true);

            if (!match) {
                System.out.println("模式串匹配失败");
                return false;
            }
        }

        // 全部匹配成功
        System.out.println("模式串匹配成功");
        return true;
    }

    public static String getMatchText(String text, int index) {
        String matchChar = "[" + text.substring(index, index + 1) + "]";
        return text.substring(0, index) + matchChar + text.substring(index + 1);
    }

    public static void printDelimiter(char delimiter, int length, boolean newLine) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; ++ i) {
            sb.append(delimiter);
        }

        System.out.print(sb);
        if (newLine) {
            System.out.println();
        }
    }
}

控制台输出：

========================================
第 1 次匹配
========================================
[A]BABACAB
[A]BACA
textIndex = 0, patternIndex = 0, 当前字符匹配结果：true
----------------------------------------
A[B]ABACAB
A[B]ACA
textIndex = 1, patternIndex = 1, 当前字符匹配结果：true
----------------------------------------
AB[A]BACAB
AB[A]CA
textIndex = 2, patternIndex = 2, 当前字符匹配结果：true
----------------------------------------
ABA[B]ACAB
ABA[C]A
textIndex = 3, patternIndex = 3, 当前字符匹配结果：false
----------------------------------------
模式串匹配失败
========================================
第 2 次匹配
========================================
A[B]ABACAB
 [A]BACA
textIndex = 1, patternIndex = 0, 当前字符匹配结果：false
----------------------------------------
模式串匹配失败
========================================
第 3 次匹配
========================================
AB[A]BACAB
  [A]BACA
textIndex = 2, patternIndex = 0, 当前字符匹配结果：true
----------------------------------------
ABA[B]ACAB
  A[B]ACA
textIndex = 3, patternIndex = 1, 当前字符匹配结果：true
----------------------------------------
ABAB[A]CAB
  AB[A]CA
textIndex = 4, patternIndex = 2, 当前字符匹配结果：true
----------------------------------------
ABABA[C]AB
  ABA[C]A
textIndex = 5, patternIndex = 3, 当前字符匹配结果：true
----------------------------------------
ABABAC[A]B
  ABAC[A]
textIndex = 6, patternIndex = 4, 当前字符匹配结果：true
----------------------------------------
模式串匹配成功
index = 2

从上面 BF 算法的执行过程，可以清晰的看到，文本串在失配（不匹配）时，textIndex 会进行回退。

2. KMP 算法

问：那么有不需要回退 textIndex 的字符串匹配算法吗？
答：有的。

2.1 术语介绍

前缀：从一个串左边第一个字符开始的一个子串。
后缀：一个串最右端字符的一个子串。
真前缀：一个串除该串自身外的其他前缀。
真后缀：一个串除该串自身外的其他后缀。

public class TermShow {
    public static void main(String[] args) {
        String text = "ABACA";
        printNextArray(text);
    }

    public static void printNextArray(String text) {
        int delimiterLength = 50;
        System.out.println("text: " + text);
        printDelimiter('=', delimiterLength);

        for (int i = 0; i < text.length(); ++i) {
            printNext(text, i);
            printDelimiter('*', delimiterLength);
        }
    }

    public static void printDelimiter(char delimiter, int length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; ++ i) {
            sb.append(delimiter);
        }
        System.out.println(sb);
    }

    public static void printNext(String text, int endIndex) {
        System.out.println("text[0," + endIndex + "]: " + text.substring(0, endIndex + 1));

        List<String> properPrefixs = getAndPrintProperPrefix(text, endIndex);
        List<String> properSuffixs = getAndPrintProperSuffix(text, endIndex);

        printMatchInfo(properPrefixs, properSuffixs);
    }

    public static List<String> getAndPrintProperPrefix(String text, int endIndex) {
        if (endIndex == 0) {
            return Collections.emptyList();
        }

        List<String> properPrefixs = new ArrayList<>();
        System.out.print("真前缀：{");
        for (int i = 0; i < endIndex; ++ i) {
            if (i != 0) {
                System.out.print(",");
            }

            String properPrefix = text.substring(0, i + 1);
            System.out.print(" " + properPrefix);

            properPrefixs.add(properPrefix);
        }
        System.out.println(" }");

        return properPrefixs;
    }

    public static List<String> getAndPrintProperSuffix(String text, int endIndex) {
        if (endIndex == 0) {
            return Collections.emptyList();
        }

        List<String> properSuffixs = new ArrayList<>();
        System.out.print("真后缀：{");
        for (int i = endIndex; i >= 1; -- i) {
            if (i != endIndex) {
                System.out.print(",");
            }

            String properSuffix = text.substring(i, endIndex + 1);
            System.out.print(" " + properSuffix);

            properSuffixs.add(properSuffix);
        }
        System.out.println(" }");

        return properSuffixs;
    }

    public static void printMatchInfo(List<String> properPrefixs, List<String> properSuffixs) {
        System.out.print("真前缀和真后缀匹配：");
        // 真前缀和真后缀的个数是一样
        int length = properPrefixs.size();
        for (int i = 0; i < length; ++ i) {
            String properPrefix = properPrefixs.get(i);
            String properSuffix = properSuffixs.get(i);
            if (properPrefix.equals(properSuffix)) {
                String format = String.format("([长度=%d], %s) ", properPrefix.length(), properPrefix);
                System.out.print(format);
            }
        }
        System.out.println();
    }
}

控制台输出：

text: ABACA
==================================================
text[0,0]: A
真前缀和真后缀匹配：
**************************************************
text[0,1]: AB
真前缀：{ A }
真后缀：{ B }
真前缀和真后缀匹配：
**************************************************
text[0,2]: ABA
真前缀：{ A, AB }
真后缀：{ A, BA }
真前缀和真后缀匹配：([长度=1], A) 
**************************************************
text[0,3]: ABAC
真前缀：{ A, AB, ABA }
真后缀：{ C, AC, BAC }
真前缀和真后缀匹配：
**************************************************
text[0,4]: ABACA
真前缀：{ A, AB, ABA, ABAC }
真后缀：{ A, CA, ACA, BACA }
真前缀和真后缀匹配：([长度=1], A) 
**************************************************

2.2 next 数组

提问：
文本串在第 i 位，模式串在第 j 位。 pattern[j] != text[i]（失配）后，模式串应该怎么移动呢？

模式串第 j 位失配，说明第 [0, j-1] 位已经匹配，因此模式串 pattern[0, j-1] 和文本串 text[i - j, i - 1] 是相等的。

找到【模式串 [0, j-1] 的真前缀】和【文本串 text[i - j, i - 1] 的真后缀】匹配的最大长度，即【模式串 [0, j-1] 的真前缀】和模式串 [0, j-1] 的真后缀】匹配的最大长度。

假设【模式串 [0, j-1] 的真前缀】和模式串 [0, j-1] 的真后缀】匹配的最大长度为 k。
有：pattern[0, k -1] == text[i - k + 1, i]
因此从模式串的第 k 位开始匹配即可，即模式串的当前指针应该跳转到 k。

我们用 next[j] = k 表示模式串第 j 位失配后，应该跳转的位置为 k。
通过以上分析，可以知道 next[j] 还可以表示为【模式串 [0, j-1] 的真前缀】和模式串 [0, j-1] 的真后缀】匹配的最大长度为 k，不匹配时 k = 0。

2.2.1 递归计算

public class NextDemo {
    public static void main(String[] args) {
        String text = "ABABCABABD";
        for(int i = 0; i < text.length(); ++ i) {
            System.out.print(text.charAt(i) + " ");
        }
        System.out.println();
        Arrays.stream(getNext(text)).forEach(v -> System.out.print(v + " "));
        System.out.println();
    }

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        // [0, -1] 和  [0, 0] 都没有【真前缀】和【真后缀】
        next[0] = 0;
        if (pattern.length() > 1) {
             next[1] = 0;
        }

        for (int j = 2; j < pattern.length(); ++ j) {
            next[j] = getNextValue(pattern, next, j-1, next[j-1]);
        }
        return next;
    }

    /**
     *      假设：next[j] = k
     *      表示 pattern[0, j-1] 子串的【真前缀】和【真后缀】匹配的最大长度为 k
     *      也就是说：
     *          (1) pattern[0, k-1] == pattern[j-1-(k-1), j-1]
     *
     *      假设：next[k] = m
     *      表示 pattern[0, k - 1] 子串的【真前缀】和【真后缀】匹配的最大长度
     *      也就是说：
     *          (2) pattern[0, m-1] == pattern[k-1-(m-1), k-1]
     *
     *      把等式 (2) 中的 k-1-(m-1) 代入等式 (1) 中，
     *      可得：
     *        0 + k-1-(m-1) = j-1-(k-1) + k-1-(m-1)
     *                      = j-1-k+1 + k-1-(m-1)
     *                      = j-1-(m-1)
     *
     *      可得：
     *          (3) pattern[0, m-1] == pattern[j-1-(m-1), j-1]
     *
     *      观察可得：等式 (1) 和等式 (3) 是同一种形式
     */
    public static int getNextValue(String pattern, int next[], int j, int k) {
        // base case
        // [0, -1] 和  [0, 0] 都没有【真前缀】和【真后缀】
        if (j < 1) return 0;

        // 计算 next[j+1]

        // case1
        // 当 pattern[k] == pattern[j] 时
        // next[j+1] = k + 1
        if (pattern.charAt(k) == pattern.charAt(j)) {
            return k + 1;
        }

        // case2
        // 当 k == 0 && pattern[k] != pattern[j] 时
        // next[j+1] = 0
        if (k == 0) {
            return 0;
        }

        // case3
        // 当 pattern[k] != pattern[j] 时
        // k = next[k]，递归计算
        return getNextValue(pattern, next, j, next[k]);
    }
}

控制台输出：

A B A B C A B A B D 
0 0 0 1 2 0 1 2 3 4

next 数组状态转移图

可以看到，模式串失配状态转移图中，在第 0 位存在循环。

2.2.2 循环计算

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        // [0, -1] 和  [0, 0] 都没有【真前缀】和【真后缀】
        next[0] = 0;
        if (pattern.length() > 1) {
             next[1] = 0;
        }

        int k = 0;
        for (int j = 2; j < pattern.length(); ++ j) {
            // 循环计算
            // 结果(1) 为 k = 0
            // 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
            while (k > 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
                k = next[k];
            }

            if (pattern.charAt(k) == pattern.charAt(j - 1)) {
                k ++;
            }

            next[j] = k;
        }
        return next;
    }

2.2.3 next[0] = -1

提问：
文本串在第 i 位，模式串在第 j 位。文本串应该怎么移动呢？

文本串的指针只在两种情况才需要移动：

(case 1)：当前位置的字符匹配成功，text[i] == pattern[j]。文本串的当前指针指向下一位（即 i++），模式串的当前指针指向下一位（即 j++）。
(case 2)：模式串第 0 位失配时，文本串的当前指针指向下一位（即 i++），模式串的当前指针保持不变。

我们发现，模式串在第 0 位失配时，模式串的指针依然指向 0，这样会导致没有办法仅通过 next[] 的值判断当前的状态。

我们可以引入一个开始状态：-1，让模式串在第 0 位失配后，转移到这个开始状态（即 next[0] = -1）。

这时上面的 (case 2) 就变成：

模式串第 0 位失配时，文本串的当前指针指向下一位（即 i++），模式串的当前指针指向下一位（即 j++）。
这样指针的移动方式就和 (case 1) 的保持了统一。

模式串第 0 位失配时，指针指向 -1

可以看到，通过引入一个开始状态 -1，模式串失配状态转移图中的循环已经不存在。

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = -1;
        int k = -1;
        for (int j = 1; j < pattern.length(); ++ j) {
            // 循环计算
            // 结果(1) 为 k = -1
            // 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
            while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
                k = next[k];
            }

            // -1 ++ 后等于 0
            // 所以 next[1] 也可以合并到循环中处理
            k ++;
            next[j] = k;
        }
        return next;
    }

控制台输出：

A B A B C A B A B D 
-1 0 0 1 2 0 1 2 3 4

2.3 kmp 匹配算法

    public int indexOf(String text, String pattern) {
        // 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
        if (pattern.equals("")) {
            return 0;
        }

        int[] next = getNext(pattern);

        int textIndex = 0;
        int patternIndex = 0;
        while (textIndex < text.length() && patternIndex < pattern.length()) {
            if (patternIndex == -1
                || text.charAt(textIndex) == pattern.charAt(patternIndex)) {
                textIndex++;
                patternIndex++;
            } else {
                patternIndex = next[patternIndex];
            }
        }

        if (patternIndex == pattern.length()) {
            return textIndex - patternIndex;
        }

        return -1;
    }

    public int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = -1;
        int k = -1;
        for (int j = 1; j < pattern.length(); ++ j) {
            // 循环计算
            // 结果(1) 为 k = -1
            // 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
            while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
                k = next[k];
            }

            // -1 ++ 后等于 0
            // 所以 next[1] 也可以合并到循环中处理
            k ++;
            next[j] = k;
        }
        return next;
    }

时间复杂度：O(m + n)，n 为 text 的长度，m 为 pattern 的长度。

2.4 打印 KMP 匹配过程

public class KMPDemo {
    public static void main(String[] args) {
        String text = "ABABACAB";
        String pattern = "ABACA";
        int i = indexOf(text, pattern);
        System.out.println("index = " + i);
    }

    public static int indexOf(String text, String pattern) {
        // 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
        if (pattern.equals("")) {
            return 0;
        }

        int[] next = getNext(pattern);

        int textIndex = 0;
        int patternIndex = 0;

        // 匹配次数
        int count = 1;

        while (textIndex < text.length() && patternIndex < pattern.length()) {
            // 打印匹配过程
            printDelimiter('*', 40, true);
            if (patternIndex == -1) {
                System.out.println(String.format("第 %d 次匹配 【patternIndex = -1】【进行下一轮匹配】", count++));
            } else {
                System.out.println(String.format("第 %d 次匹配", count++));
                System.out.println(getMatchText(text, textIndex));
                printDelimiter(' ', textIndex - patternIndex, false);
                System.out.println(getMatchText(pattern, patternIndex));

                boolean match = text.charAt(textIndex) == pattern.charAt(patternIndex);
                System.out.println(String.format("textIndex = %d, patternIndex = %d, 当前字符匹配结果：%s", textIndex, patternIndex, match));
            }

            if (patternIndex == -1
                || text.charAt(textIndex) == pattern.charAt(patternIndex)) {
                textIndex++;
                patternIndex++;
            } else {
                patternIndex = next[patternIndex];
            }
        }

        if (patternIndex == pattern.length()) {
            return textIndex - patternIndex;
        }

        return -1;
    }

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = -1;
        int k = -1;
        for (int j = 1; j < pattern.length(); ++ j) {
            // 循环计算
            // 结果(1) 为 k = -1
            // 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
            while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
                k = next[k];
            }

            // -1 ++ 后等于 0
            // 所以 next[1] 也可以合并到循环中处理
            k ++;
            next[j] = k;
        }
        return next;
    }

    public static String getMatchText(String text, int index) {
        String matchChar = "[" + text.substring(index, index + 1) + "]";
        return text.substring(0, index) + matchChar + text.substring(index + 1);
    }

    public static void printDelimiter(char delimiter, int length, boolean newLine) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; ++ i) {
            sb.append(delimiter);
        }

        System.out.print(sb);
        if (newLine) {
            System.out.println();
        }
    }

}

控制台输出：

****************************************
第 1 次匹配
[A]BABACAB
[A]BACA
textIndex = 0, patternIndex = 0, 当前字符匹配结果：true
****************************************
第 2 次匹配
A[B]ABACAB
A[B]ACA
textIndex = 1, patternIndex = 1, 当前字符匹配结果：true
****************************************
第 3 次匹配
AB[A]BACAB
AB[A]CA
textIndex = 2, patternIndex = 2, 当前字符匹配结果：true
****************************************
第 4 次匹配
ABA[B]ACAB
ABA[C]A
textIndex = 3, patternIndex = 3, 当前字符匹配结果：false
****************************************
第 5 次匹配
ABA[B]ACAB
  A[B]ACA
textIndex = 3, patternIndex = 1, 当前字符匹配结果：true
****************************************
第 6 次匹配
ABAB[A]CAB
  AB[A]CA
textIndex = 4, patternIndex = 2, 当前字符匹配结果：true
****************************************
第 7 次匹配
ABABA[C]AB
  ABA[C]A
textIndex = 5, patternIndex = 3, 当前字符匹配结果：true
****************************************
第 8 次匹配
ABABAC[A]B
  ABAC[A]
textIndex = 6, patternIndex = 4, 当前字符匹配结果：true
index = 2

[一文说透] KMP 字符串匹配算法

1. BF 算法（Brute Force）

2. KMP 算法

2.1 术语介绍

2.2 next 数组

2.2.1 递归计算

2.2.2 循环计算

2.2.3 next[0] = -1

2.3 kmp 匹配算法

2.4 打印 KMP 匹配过程

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读