本文共 2790 字，大约阅读时间需要 9 分钟。

字符串匹配的KMP算法

朴素模式匹配算法

在进行模式匹配之前，我们需要了解什么是模式匹配。模式匹配，又称串匹配，是将模式串T从目标串S中搜索的过程。通常，主串称为目标串S，模式串称为T。以下是朴素的模式匹配算法（BF算法）的实现过程：

BF算法实现

public static int violentMatching(String s, String t) {    int i = 0;    int j = 0;    while (i < s.length() && j < t.length()) {        if (s.charAt(i) == t.charAt(j)) {            i++;            j++;        } else {            i = i - j + 1;            j = 0;        }    }    if (j == t.length()) {        return i - j;    } else {        return -1;    }}

问题分析：

尽管BF算法实现简单，但它存在效率低下的问题。例如，当模式串与主串在某个位置不相同时，BF算法会从目标串的下一个字符重新开始比较，这可能导致大量不必要的比较操作。

KMP算法：优化模式匹配

KMP算法通过预处理模式串T，构建一个辅助数组next，使得在匹配过程中能够快速定位下一个比较的位置，无需对主串S进行回溯。具体来说，KMP算法的优化措施包括：

next数组的构建

public static int[] getNext(String t) {    int[] next = new int[t.length()];    int suffix = 0;    int prefix = -1;    next[0] = -1;    while (suffix < t.length() - 1) {        if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {            prefix++;            suffix++;            next[suffix] = prefix;        } else {            prefix = next[prefix];            suffix++;            if (t.charAt(prefix) == t.charAt(suffix)) {                prefix++;                suffix++;                next[suffix] = prefix;            } else {                next[suffix] = -1;            }        }    }    return next;}

解释：

KMP匹配过程

public static int KMP(String s, String t) {    int i = 0;    int j = 0;    int[] next = getNext(t);    while (i < s.length() && j < t.length()) {        if (j == -1 || s.charAt(i) == t.charAt(j)) {            i++;            j++;        } else {            j = next[j];        }    }    if (j == t.length()) {        return i - j;    } else {        return -1;    }}

解释：

优化版本：处理特殊情况

public static int[] getNext(String t) {    int[] next = new int[t.length()];    int[] maxLen = new int[t.length()];    int suffix = 0;    int prefix = -1;    next[0] = -1;    while (suffix < t.length() - 1) {        if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {            prefix++;            suffix++;            next[suffix] = prefix;        } else {            next[suffix] = next[prefix];            if (t.charAt(prefix) != t.charAt(suffix)) {                prefix = -1;            } else {                suffix++;                prefix++;            }        }    }    return next;}

改进点：

• 当字符相同时，利用旧next值继续比较，避免不必要的回溯。
• 处理字符不匹配的情况，直接跳转到下一个位置，确保高效匹配。

总结

KMP算法通过预处理模式串T，构建next数组来优化模式匹配过程。这种预处理使得算法在匹配过程中无需对主串S进行回溯，只需对模式串T进行回溯，从而显著提升了效率。KMP算法的优化使它成为处理大规模字符串匹配问题的首选算法。