编程导航会员会员
登录/注册

一文带你学会"KMP 算法"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

KMP 算法

介绍

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，核心思想是利用已经部分匹配的信息，避免重复比较，在文本串中快速查找模式串。KMP算法特别适合处理长文本和重复性高的模式串，时间复杂度是O(m+n)，m是模式串长度，n是文本串长度。

KMP算法的关键在于构建一个部分匹配表（也叫失败函数或者next数组），这个表记录了当匹配失败时，模式串指针应该回退到的位置，让算法跳过已知不可能匹配的位置，提高匹配效率。

算法步骤

KMP算法主要分为两个阶段：

  1. 预处理阶段：计算模式串的部分匹配表（next数组）
    • 构建一个数组，记录每个位置的最长相等前后缀长度
    • 该数组用于在匹配失败时确定模式串指针的回退位置
  2. 匹配阶段：使用部分匹配表在文本串中查找模式串
    • 从左到右同时遍历文本串和模式串
    • 当字符不匹配时，根据next数组回退模式串指针
    • 当模式串完全匹配时，记录匹配位置并继续查找其他匹配

核心特性

  • 线性时间复杂度：O(m+n)，其中m是模式串长度，n是文本串长度
  • 高效利用历史信息：通过预处理避免了重复比较
  • 只需一次遍历文本串：文本串指针不会回退
  • 空间复杂度：O(m)，仅需存储模式串的部分匹配表
  • 适用场景：特别适合长文本和具有重复性的模式串

基础实现

暴力解法

先看下暴力解法：

▼
java
复制代码
public class NaiveStringMatcher {
    
    /**
     * 朴素字符串匹配算法
     * @param text 文本串
     * @param pattern 模式串
     * @return 匹配成功则返回模式串在文本串中的起始位置，否则返回-1
     */
    public static int naiveSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        // 特殊情况处理
        if (m == 0) return 0;
        if (n < m) return -1;
        
        // 尝试所有可能的匹配位置
        for (int i = 0; i <= n - m; i++) {
            int j;
            
            // 从当前位置开始比较模式串和文本串
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // 发现不匹配字符，终止内层循环
                }
            }
            
            // 如果j等于m，说明模式串完全匹配
            if (j == m) {
                return i; // 返回匹配位置
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 使用示例
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int position = naiveSearch(text, pattern);
        
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 处匹配");
        }
    }
}

上述实现暴力枚举所有可能的匹配位置，逐一比较文本串与模式串的每个字符，直到找到完全匹配或确定不存在匹配。

接下来展示KMP算法的实现：

Java实现

▼
java
复制代码
public class KMP {
    // 构建部分匹配表（next数组）
    private static int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0; // 第一个字符的最长相等前后缀长度为0
        
        for (int i = 1, j = 0; i < m; i++) {
            // 当前字符不匹配，回退j
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 当前字符匹配，j向前移动
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 记录当前位置的最长相等前后缀长度
            next[i] = j;
        }
        
        return next;
    }
    
    // KMP搜索算法
    public static int kmpSearch(String text, String pattern) {
        if (pattern == null || pattern.length() == 0) {
            return 0;
        }
        
        if (text == null || text.length() < pattern.length()) {
            return -1;
        }
        
        int n = text.length();
        int m = pattern.length();
        
        // 构建next数组
        int[] next = buildNext(pattern);
        
        // 进行匹配
        for (int i = 0, j = 0; i < n; i++) {
            // 当前字符不匹配，根据next数组回退j
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 当前字符匹配，j向前移动
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 完全匹配，返回起始索引
            if (j == m) {
                return i - m + 1;
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 查找所有匹配位置
    public static List<Integer> kmpSearchAll(String text, String pattern) {
        List<Integer> positions = new ArrayList<>();
        if (pattern == null || pattern.length() == 0) {
            return positions;
        }
        
        if (text == null || text.length() < pattern.length()) {
            return positions;
        }
        
        int n = text.length();
        int m = pattern.length();
        
        // 构建next数组
        int[] next = buildNext(pattern);
        
        // 进行匹配
        for (int i = 0, j = 0; i < n; i++) {
            // 当前字符不匹配，回退j
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 当前字符匹配，j向前移动
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 完全匹配，记录位置并继续匹配
            if (j == m) {
                positions.add(i - m + 1);
                // 回退j以寻找下一个匹配
                j = next[j - 1];
            }
        }
        
        return positions;
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int pos = kmpSearch(text, pattern);
        List<Integer> allPos = kmpSearchAll(text, pattern);
        
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("首次匹配位置: " + (pos != -1 ? pos : "未找到"));
        System.out.println("所有匹配位置: " + allPos);
        
        // 打印next数组，帮助理解
        int[] next = buildNext(pattern);
        System.out.print("next数组: ");
        for (int val : next) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

在上述代码中，

▼
java
复制代码
// 当前字符不匹配，回退j
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
    j = next[j - 1];
}

是 KMP 算法的核心，在匹配失败时根据预先计算的next数组来确定模式串指针的回退位置。

JavaScript 实现

▼
javascript
复制代码
function buildNext(pattern) {
    const m = pattern.length;
    const next = new Array(m).fill(0);
    
    for (let i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[i] !== pattern[j]) {
            j = next[j - 1];
        }
        
        if (pattern[i] === pattern[j]) {
            j++;
        }
        
        next[i] = j;
    }
    
    return next;
}

function kmpSearch(text, pattern) {
    if (!pattern || pattern.length === 0) {
        return 0;
    }
    
    if (!text || text.length < pattern.length) {
        return -1;
    }
    
    const n = text.length;
    const m = pattern.length;
    const next = buildNext(pattern);
    
    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] !== pattern[j]) {
            j = next[j - 1];
        }
        
        if (text[i] === pattern[j]) {
            j++;
        }
        
        if (j === m) {
            return i - m + 1;
        }
    }
    
    return -1;
}

// 测试
const text = "ABABDABACDABABCABAB";
const pattern = "ABABCABAB";
console.log(`文本: ${text}`);
console.log(`模式: ${pattern}`);
console.log(`匹配位置: ${kmpSearch(text, pattern)}`);
console.log(`next数组: ${buildNext(pattern).join(' ')}`);

Python 实现

▼
python
复制代码
def build_next(pattern):
    m = len(pattern)
    next_array = [0] * m
    
    for i in range(1, m):
        j = next_array[i - 1]
        
        while j > 0 and pattern[i] != pattern[j]:
            j = next_array[j - 1]
        
        if pattern[i] == pattern[j]:
            j += 1
        
        next_array[i] = j
    
    return next_array

def kmp_search(text, pattern):
    if not pattern:
        return 0
    
    if not text or len(text) < len(pattern):
        return -1
    
    n, m = len(text), len(pattern)
    next_array = build_next(pattern)
    
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next_array[j - 1]
        
        if text[i] == pattern[j]:
            j += 1
        
        if j == m:
            return i - m + 1
    
    return -1

# 测试
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(f"文本: {text}")
print(f"模式: {pattern}")
print(f"匹配位置: {kmp_search(text, pattern)}")
print(f"next数组: {build_next(pattern)}")

Go 实现

▼
go
复制代码
package main

import "fmt"

func buildNext(pattern string) []int {
    m := len(pattern)
    next := make([]int, m)
    
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && pattern[i] != pattern[j] {
            j = next[j-1]
        }
        
        if pattern[i] == pattern[j] {
            j++
        }
        
        next[i] = j
    }
    
    return next
}

func kmpSearch(text, pattern string) int {
    if len(pattern) == 0 {
        return 0
    }
    
    if len(text) < len(pattern) {
        return -1
    }
    
    n, m := len(text), len(pattern)
    next := buildNext(pattern)
    
    for i, j := 0, 0; i < n; i++ {
        for j > 0 && text[i] != pattern[j] {
            j = next[j-1]
        }
        
        if text[i] == pattern[j] {
            j++
        }
        
        if j == m {
            return i - m + 1
        }
    }
    
    return -1
}

func main() {
    text := "ABABDABACDABABCABAB"
    pattern := "ABABCABAB"
    
    fmt.Println("文本:", text)
    fmt.Println("模式:", pattern)
    fmt.Println("匹配位置:", kmpSearch(text, pattern))
    fmt.Println("next数组:", buildNext(pattern))
}

C 实现

▼
c
复制代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void buildNext(const char* pattern, int* next, int m) {
    next[0] = 0;
    
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        if (pattern[i] == pattern[j]) {
            j++;
        }
        
        next[i] = j;
    }
}

int kmpSearch(const char* text, const char* pattern) {
    if (pattern == NULL || strlen(pattern) == 0) {
        return 0;
    }
    
    if (text == NULL || strlen(text) < strlen(pattern)) {
        return -1;
    }
    
    int n = strlen(text);
    int m = strlen(pattern);
    int* next = (int*)malloc(m * sizeof(int));
    
    buildNext(pattern, next, m);
    
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        if (text[i] == pattern[j]) {
            j++;
        }
        
        if (j == m) {
            free(next);
            return i - m + 1;
        }
    }
    
    free(next);
    return -1;
}

int main() {
    const char* text = "ABABDABACDABABCABAB";
    const char* pattern = "ABABCABAB";
    
    printf("文本: %s\n", text);
    printf("模式: %s\n", pattern);
    
    int pos = kmpSearch(text, pattern);
    printf("匹配位置: %d\n", pos);
    
    // 打印next数组
    int m = strlen(pattern);
    int* next = (int*)malloc(m * sizeof(int));
    buildNext(pattern, next, m);
    
    printf("next数组: ");
    for (int i = 0; i < m; i++) {
        printf("%d ", next[i]);
    }
    printf("\n");
    
    free(next);
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> buildNext(const string& pattern) {
    int m = pattern.length();
    vector<int> next(m, 0);
    
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        if (pattern[i] == pattern[j]) {
            j++;
        }
        
        next[i] = j;
    }
    
    return next;
}

int kmpSearch(const string& text, const string& pattern) {
    if (pattern.empty()) {
        return 0;
    }
    
    if (text.length() < pattern.length()) {
        return -1;
    }
    
    int n = text.length();
    int m = pattern.length();
    vector<int> next = buildNext(pattern);
    
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        
        if (text[i] == pattern[j]) {
            j++;
        }
        
        if (j == m) {
            return i - m + 1;
        }
    }
    
    return -1;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    
    cout << "文本: " << text << endl;
    cout << "模式: " << pattern << endl;
    
    int pos = kmpSearch(text, pattern);
    cout << "匹配位置: " << pos << endl;
    
    vector<int> next = buildNext(pattern);
    cout << "next数组: ";
    for (int val : next) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

优化策略

优化next数组

▼
java
复制代码
// 优化next数组，避免匹配失败后回退到同样会失败的位置
private static int[] buildOptimizedNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = 0;
    
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        // 当前位置匹配失败时，如果回退位置的字符与当前位置相同，则继续回退
        if (i + 1 < m && pattern.charAt(i + 1) == pattern.charAt(j)) {
            next[i] = next[j - 1];
        } else {
            next[i] = j;
        }
    }
    
    return next;
}

预处理减少分支

▼
java
复制代码
// 预处理字符映射，减少字符比较的分支
public static int kmpSearchOptimized(String text, String pattern) {
    if (pattern == null || pattern.length() == 0) {
        return 0;
    }
    
    if (text == null || text.length() < pattern.length()) {
        return -1;
    }
    
    int n = text.length();
    int m = pattern.length();
    
    // 使用数组映射来加速字符比较（假设字符集为ASCII）
    // 为每个模式字符的每个位置创建一个状态转移表
    int[][] dfa = new int[256][m];
    
    // 初始化第一个字符的DFA
    dfa[pattern.charAt(0)][0] = 1;
    
    for (int X = 0, j = 1; j < m; j++) {
        // 复制匹配失败情况下的值
        for (int c = 0; c < 256; c++) {
            dfa[c][j] = dfa[c][X];
        }
        // 设置匹配成功情况下的值
        dfa[pattern.charAt(j)][j] = j + 1;
        // 更新重启状态
        X = dfa[pattern.charAt(j)][X];
    }
    
    // 模式匹配
    int i, j;
    for (i = 0, j = 0; i < n && j < m; i++) {
        j = dfa[text.charAt(i)][j];
    }
    
    if (j == m) {
        return i - m; // 找到匹配
    } else {
        return -1;    // 未找到匹配
    }
}

优缺点

优点

  • 时间复杂度为O(m+n)，优于朴素的字符串匹配算法(暴力解法)
  • 文本串只需扫描一次，不会回退
  • 对于包含重复模式的字符串会高效
  • 预处理模式串，可以多次用于不同的文本串
  • 能快速跳过已知不会匹配的位置

缺点

  • 需要额外的空间存储next数组
  • 构建next数组的逻辑较为复杂，不易理解
  • 在模式串较短或无重复模式时，相比简单算法优势不明显
  • 实现时容易出错，特别是处理边界情况

应用场景

1）生物信息学中的DNA序列匹配

2）网络入侵检测系统中的模式匹配

3）搜索引擎的关键词匹配

4）数据压缩算法中的模式识别

扩展

多模式字符串匹配

▼
java
复制代码
// Aho-Corasick算法 - KMP的多模式扩展
public static class AhoCorasick {
    static class TrieNode {
        TrieNode[] children = new TrieNode[256];
        TrieNode fail;
        List<Integer> patternIndices = new ArrayList<>();
        
        public TrieNode() {
            fail = null;
        }
    }
    
    private TrieNode root;
    private String[] patterns;
    
    public AhoCorasick(String[] patterns) {
        this.patterns = patterns;
        buildTrie();
        buildFailureLinks();
    }
    
    private void buildTrie() {
        root = new TrieNode();
        
        for (int i = 0; i < patterns.length; i++) {
            String pattern = patterns[i];
            TrieNode node = root;
            
            for (char c : pattern.toCharArray()) {
                if (node.children[c] == null) {
                    node.children[c] = new TrieNode();
                }
                node = node.children[c];
            }
            
            node.patternIndices.add(i);
        }
    }
    
    private void buildFailureLinks() {
        Queue<TrieNode> queue = new LinkedList<>();
        
        // 初始化根节点的子节点
        for (int i = 0; i < 256; i++) {
            if (root.children[i] != null) {
                root.children[i].fail = root;
                queue.offer(root.children[i]);
            } else {
                root.children[i] = root;
            }
        }
        
        // BFS构建失败链接
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            
            for (int i = 0; i < 256; i++) {
                if (node.children[i] != null) {
                    TrieNode failNode = node.fail;
                    
                    while (failNode != root && failNode.children[i] == null) {
                        failNode = failNode.fail;
                    }
                    
                    failNode = failNode.children[i];
                    node.children[i].fail = failNode;
                    
                    // 合并匹配结果
                    node.children[i].patternIndices.addAll(failNode.patternIndices);
                    
                    queue.offer(node.children[i]);
                }
            }
        }
    }
    
    public List<Pair<Integer, Integer>> search(String text) {
        List<Pair<Integer, Integer>> results = new ArrayList<>();
        TrieNode currentState = root;
        
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            
            while (currentState != root && currentState.children[c] == null) {
                currentState = currentState.fail;
            }
            
            currentState = currentState.children[c];
            
            for (int patternIndex : currentState.patternIndices) {
                int endPos = i;
                int startPos = endPos - patterns[patternIndex].length() + 1;
                results.add(new Pair<>(patternIndex, startPos));
            }
        }
        
        return results;
    }
    
    static class Pair<K, V> {
        K first;
        V second;
        
        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }
    }
}

近似字符串匹配（编辑距离）

▼
java
复制代码
public static int[] kmpWithEditDistance(String text, String pattern, int maxDistance) {
    int n = text.length();
    int m = pattern.length();
    List<Integer> matches = new ArrayList<>();
    
    // 使用动态规划结合KMP思想
    for (int i = 0; i <= n - m; i++) {
        int distance = 0;
        
        for (int j = 0; j < m && distance <= maxDistance; j++) {
            if (text.charAt(i + j) != pattern.charAt(j)) {
                distance++;
            }
        }
        
        if (distance <= maxDistance) {
            matches.add(i);
        }
    }
    
    // 转换为数组
    int[] result = new int[matches.size()];
    for (int i = 0; i < matches.size(); i++) {
        result[i] = matches.get(i);
    }
    
    return result;
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

  1. KMP算法的时间复杂度是多少？它与暴力匹配算法的主要区别是什么？
  2. KMP算法中next数组的含义是什么？如何利用它避免不必要的比较？
  3. 在KMP算法中，文本指针是否会回退？为什么？

测验答案

  1. KMP算法的时间复杂度是O(m+n)，其中m是模式串长度，n是文本串长度。与暴力匹配算法O(m*n)相比，KMP算法利用已匹配信息避免重复比较，文本指针不会回退。
  2. next数组记录了模式串中每个位置的最长相等前后缀长度，表示当匹配失败时，模式串指针应该回退到的位置。通过跳过已知不可能匹配的位置，实现减少不必要的比较次数。
  3. 文本指针不会回退，只有模式串指针会根据next数组回退。因为KMP算法的核心思想就是利用已经部分匹配的信息，避免对文本串的重复扫描。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的 LeetCode 题目：

KMP算法是字符串处理中的经典算法，用来解决字符串匹配问题，理解它对提升算法设计能力还是很有帮助的。

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"最近点对问题"
4
一文带你学会"分治算法"
4
一文带你学会"Boyer-Moore算法"
3
一文带你学会"Rabin-Karp算法"
3
一文带你学会"哈希查找"
2
下载 APP