经典算法之KMP算法(C++代码)

m0_74013450

2574人浏览 · 2025-04-06 11:16:46

m0_74013450 · 2025-04-06 11:16:46 发布

KMP算法是字符串匹配领域的重要算法，由Knuth、Morris和Pratt三位计算机科学家共同提出

基本原理：

KMP 算法的核心思想是利用已经匹配过的部分信息，避免不必要的回溯，从而提高匹配效率。在匹配过程中，当模式串中的某个字符与主串中的字符不匹配时，不是简单地将模式串后移一位重新开始匹配，而是根据模式串本身的特点，计算出模式串中需要向后移动的位数，使得模式串尽可能多地利用已经匹配过的信息，继续进行匹配。

1.字符串匹配问题

字符串匹配是计算机科学中的基础问题，给定一个文本串T（主串）和模式串P，我们需要在T中找出所有P出现的位置

传统暴力匹配法

实现简单直观，代码逻辑清晰，容易理解和编写，对于简单的字符串匹配场景，如果对效率要求不高，使用传统匹配法可以快速实现功能。

根据以上例题代码如下（主串t,模式串p,t.size()>p.size()）

int bf(string t, string p) {
    int n = t.size(), m = p.size();
    for(int i = 0; i <= n - m; i++) {
        int j = 0;
        while(j < m && t[i+j] == p[j]) j++;
        if(j == m) return i;
    }
    return -1;
}

在最坏情况下，对于主串长度为m，模式串长度为n，每次匹配都需要从主串的每个位置开始依次与模式串进行比较，时间复杂度为O(mn)。例如，主串为 “aaaaaaaab”，模式串为 “aaab”，每次都要比较到模式串的最后一位才能发现不匹配，然后主串指针后移一位继续匹配，效率较低。

2.KMP算法处理字符串匹配问题

通过利用已经匹配过的信息，避免了不必要的回溯，时间复杂度为O(m+n)。无论主串和模式串的内容如何，都能在接近线性的时间内完成匹配。

一.简单介绍

核心步骤（构建next数组）

KMP算法的核心在于利用已匹配的信息避免不必要的比较。它通过预处理模式串，构建一个部分匹配表(Partial Match Table)，也称为"失败函数"(failure function)或"next数组"。

还是上面的主串t,模式串p字符串匹配问题，下面是使用动画演示传统暴力匹配与kmp算法的比较（动画做的不是很好，凑合着先看加深一下理解，后面会优化）

##CIF图片可能有点模糊（真不是有意的，小博主找了许久才在网上找到一个免费版的视频转GIF图片网站），需要更清楚的演示动画，记得在评论区留言，我看反映的人多，会后续单独出一篇文章免费分享网页版动画源码，感谢大家支持！！！

传统暴力匹配

kmp算法

观察kmp算法主串上的指针是没有回退的，这是kmp算法的优点之一。

二.next数组的构建

next数组概念

next 数组（部分匹配表）的构建是核心环节，它能够让我们在字符串匹配时避免主串指针回退，提升匹配效率。next 数组记录的是模式串每个位置之前的子串的最长公共前后缀的长度。下面详细介绍 next 数组的构建方法。

注：next数组是基于模式串建立的，作用在模式串上

前置知识概念（需要掌握）

（1）前缀与后缀：
前缀指的是除了最后一个字符之外，一个字符串的所有头部子串。例如，字符串 "abc" 的前缀有 "a"、"ab"。
后缀指的是除了第一个字符之外，一个字符串的所有尾部子串。例如，字符串 "abc" 的后缀有 "bc"、"c"。
（2）最长公共前后缀：

对于一个字符串，其最长公共前后缀就是前缀和后缀中相同且长度最长的子串。例如，字符串 "abab" 的最长公共前后缀是 "ab"，长度为 2。

注：全部ptm值组成的数组就是next数组

例如模式串"ababc"

构建next数组的代码实现

(1)构建next数组

vector<int> gen(const string& p) {
    int m = p.size();
    vector<int> nxt(m + 1);  // 多一位用于完整模式串的匹配
    nxt[0] = -1;
    int i = 0, j = -1;
    
    while (i < m) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            nxt[i] = j;
        } else {
            j = nxt[j];
        }
    }
    
    return nxt;
}

(2)构建next数组优化

vector<int> gen_opt(const string& p) {
    int m = p.size();
    vector<int> nxt(m + 1);
    nxt[0] = -1;
    int i = 0, j = -1;
    
    while (i < m) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            // 优化：如果字符相同，直接继承next值
            nxt[i] = (p[i] != p[j]) ? j : nxt[j];
        } else {
            j = nxt[j];
        }
    }
    
    return nxt;
}

3.KMP代码

还是上面那个例子：给定一个文本串T和模式串P，我们需要在T中找出所有P出现的位置。

结合上面next数组的构建实现

int kmp(string t, string p) {
    int n = t.size(), m = p.size();
    if(m == 0) return 0;
    auto nxt = gen(p);
    int i = 0, j = 0;
    while(i < n && j < m) {
        if(j == -1 || t[i] == p[j]) {
            i++; j++;
        } else {
            j = nxt[j];
        }
    }
    return j == m ? i - j : -1;
}

KMP算法时间复杂度分析

预处理阶段：构建next数组，时间复杂度O(m)
搜索阶段：匹配过程，时间复杂度O(n)
总时间复杂度为O(n+m)，远优于暴力算法的O(n*m)。

KMP算法优化

（1）上面next数组的优化算一种优化策略

（2）KMP可以扩展为AC自动机算法，用于多模式串匹配：

struct Node {
    vector<int> ch;
    int fail;
    vector<int> out;
    Node() : ch(26, -1), fail(-1) {}
};

vector<Node> build(vector<string> ps) {
    vector<Node> trie(1);
    // 构建trie树
    for(int i = 0; i < ps.size(); i++) {
        int u = 0;
        for(char c : ps[i]) {
            int id = c - 'a';
            if(trie[u].ch[id] == -1) {
                trie[u].ch[id] = trie.size();
                trie.emplace_back();
            }
            u = trie[u].ch[id];
        }
        trie[u].out.push_back(i);
    }
    // 构建fail指针
    queue<int> q;
    for(int i = 0; i < 26; i++) {
        if(trie[0].ch[i] != -1) {
            q.push(trie[0].ch[i]);
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i++) {
            int v = trie[u].ch[i];
            if(v == -1) continue;
            int f = trie[u].fail;
            while(f != -1 && trie[f].ch[i] == -1) {
                f = trie[f].fail;
            }
            trie[v].fail = (f == -1) ? 0 : trie[f].ch[i];
            q.push(v);
        }
    }
    return trie;
}

KMP算法的知识就分享到这里，对你有帮助的话麻烦点个赞支持一下，非常感谢，喜欢研究算法可以点个关注，后续会持续更新算法知识分享