KMP算法入门

朴素算法（Brute-Force）会从主串的每一个位置开始，逐个字符与模式串比对，失配则将主串指针回退，时间复杂度可达。：失配时，已匹配的部分信息被完全丢弃，主串指针的回溯导致了重复扫描。KMP（Knuth-Morris-Pratt）算法的精髓在于。（且前缀不能等于整个子串，即严格真前缀/真后缀）。的仅含小写字母的字符串中恰好出现了两次。处继续尝试匹配，从而避免重复比较。将模式串与自身进行匹配，递

2401_88204232

291人浏览 · 2026-04-22 18:19:58

2401_88204232 · 2026-04-22 18:19:58 发布

KMP 算法深度解析与模板 && 上手实践

`Part 1:原理讲解:`

1. 问题背景与暴力匹配的困境

字符串匹配问题要求在长度为 $n$ 的主串 s 中，找出所有长度为 $m$ 的模式串 p 的出现位置。朴素算法（Brute-Force）会从主串的每一个位置开始，逐个字符与模式串比对，失配则将主串指针回退，时间复杂度可达 $O (nm)$ ，在长文本场景下效率低下。

根本原因：失配时，已匹配的部分信息被完全丢弃，主串指针的回溯导致了重复扫描。

2. KMP 核心思想：前缀函数与自动机跳转

KMP（Knuth-Morris-Pratt）算法的精髓在于 利用模式串自身的结构信息，使得匹配失败时，主串指针 $i$ 永不回退，模式串指针 $j$ 智能回退。

对于模式串 p，我们预处理出一个 前缀函数（通常记为 next 数组）：

next[j] 表示 模式串前 $j$ 个字符构成的子串中，最长的、相等的前缀与后缀的长度（且前缀不能等于整个子串，即严格真前缀/真后缀）。

当匹配进行到 s[i] 与 p[j+1] 失配时，说明：

前 $j$ 个字符已经匹配成功；
这 $j$ 个字符既是主串当前窗口的后缀，也是模式串的前缀。

此时，我们无需将 $i$ 回退，而是令 $j = n e x t [j]$ ，将模式串向右滑动至 最长可匹配前缀 处继续尝试匹配，从而避免重复比较。

3. 模板代码结构说明

本模板采用 字符串下标从 $1$ 开始 的约定，方便与 next 数组的定义对齐。变量命名遵循经典写法：

s[N]：主串，下标 $\dots n$ 。
p[N]：模式串，下标 $\dots m$ 。
ne[M]：前缀函数数组，ne[j] 表示模式串前 $j$ 个字符的最长相等前后缀长度。
主串指针 i，模式串指针 j 均从 $1$ 开始，j=0 表示当前无任何匹配字符。

4. 步骤一：求解 `next` 数组（自匹配）

将模式串与自身进行匹配，递推地计算 ne 数组。

// 求模式串的next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

代码逻辑拆解表格

代码语句	作用
`i = 2, j = 0`	`i` 从第二个字符开始扫描模式串，`j` 初始化为 0，表示当前无匹配前缀。
`while (j && p[i] != p[j + 1])`	若失配且 `j > 0`，利用 `ne` 数组回溯 `j`，直到找到可匹配位置或 `j = 0`。
`if (p[i] == p[j + 1])`	匹配成功时，扩展当前匹配的前缀长度，`j` 增加 1。
`ne[i] = j`	记录前 `i` 个字符的最长相等前后缀长度。

算法分析

时间复杂度： $O (m)$ ，其中 $m$ 为模式串长度。每个字符的 j 最多增加 1 次，回溯总次数为线性。
核心逻辑：通过动态维护 ne 数组，利用已计算的部分匹配信息快速跳转，避免重复匹配。

5. 步骤二：主串与模式串匹配

利用已构建好的 next 数组，在主串 s 中进行线性扫描匹配。

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

代码逻辑拆解表格

语句	作用
`i = 1, j = 0`	初始化指针，`i` 扫描主串 `s`，`j` 表示已匹配的模式串 `p` 的字符个数。
`while (j && s[i] != p[j + 1])`	失配时，根据 `ne` 数组回退 `j`，主串指针 `i` 保持不动。
`if (s[i] == p[j + 1])`	匹配成功时，`j` 后移一位，继续匹配下一个字符。
`if (j == m)`	找到完整匹配后记录结果，并将 `j` 设为 `ne[j]`，以允许重叠匹配。

补充说明

ne 数组：存储模式串 p 的部分匹配信息（如 KMP 算法中的最长公共前后缀长度），用于快速回退 j。
重叠匹配：通过 j = ne[j] 保留部分已匹配内容，避免重复扫描主串。

6.完整模板（来自y神）

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

@@@

###魔法传送门:

`Part 2:上手实训:`

P10581 [蓝桥杯 2024 国 A] 重复的串

题目描述

给定一个仅含小写字母的字符串 $S$ ，问有多少个长度为 $n$ 的仅含小写字母的字符串中恰好出现了两次 $S$ 。答案对 $998\ 244\ 353$ 取模。

输入格式

输入一行包含一个字符串 $S$ 和一个整数 $n$ ，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

aba 6

输出 #1

输入输出样例 #2

输入 #2

aba 10

输出 #2

77907666

说明/提示

对于 $40\%$ 的评测用例， $\le 20$ ， $\le 6$ ；
另有 $10\%$ 的评测用例， $n\le 500$ ， $\le 2$ ；
对于 $70\%$ 的评测用例， $n\le 10^5$ ；
对于所有评测用例， $1\le n\le 10^9$ ， $\le |S| \le 30$ 。

我们来思考一下：

暴力 DP 设计与局限性分析

定义三维状态 dp[i][j][cnt]：

i：构造出的随机串长度
j：KMP 自动机中当前与模式串的最长匹配长度
cnt：模式串完整匹配的次数（限制 0 ≤ cnt ≤ 2）

初始条件：

dp[0][0][0] = 1（空串、无匹配、方案唯一）

转移逻辑：

枚举串长 i、匹配位置 j、匹配次数 cnt
枚举下一位 26 个小写字母

利用 KMP 核心逻辑更新匹配长度 cur：

int cur = j;
while (cur && pat[cur + 1] != ch) cur = ne[cur];
if (pat[cur + 1] == ch) cur++;

匹配结果处理：

若 cur = m，触发完整匹配：
- 若 cnt < 2，匹配次数 cnt + 1，跳转至 next[m]
若 cur < m，仅更新匹配位置 j = cur

时间复杂度：

O(n × 3 × m × 26)，无法处理 n 极大的情况

优化突破口：转移固定性分析

关键性质：

状态转移与字符串长度 i 无关
相同 (j, cnt) 状态下填入相同字母，跳转结果唯一
适用矩阵加速递推：多维度小状态 + 大步数递推 + 固定转移规则

矩阵加速具体实现思路

状态压缩

状态二元组 (j, cnt)：
- j 范围 0 ≤ j < m
- cnt 范围 0, 1, 2
压缩为一维编号：
- 基准偏移 base = 1 + cnt * (m + 1)
- 状态编号 now_id = base + j

构造转移矩阵

矩阵元素 trans[u][v]：从状态 u 转移到 v 的方案数
遍历合法状态和 26 个字母：
- 触发完整匹配且 cnt < 2：跳转至下一层
- 未触发匹配：更新匹配位置
- cnt = 2：禁止转移

矩阵快速幂优化

转移 n 次等价于矩阵的 n 次幂
复杂度：O((3m)^3 log n)

初始状态与答案统计

初始向量：dp[0][0][0] = 1
最终统计：所有 cnt = 2 的状态方案数之和

关键细节补充

KMP 预处理：
- 模式串 1 下标存储
- 预处理 next 数组
取模处理：
- 所有运算对 998244353 取模
匹配后跳转：
- 强制跳转 next[m]，避免重叠匹配重复统计
边界限制：
- 严格限制匹配次数不超过 2

复杂度对比

暴力 DP：O(n × m)（超时）
矩阵优化：O((3m)^3 log n)（高效处理大数据）

香喷喷的可食用代码上菜咯~

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAX_STATE = 105;   // 最大状态数，足够用
const int MAX_PAT = 35;      // 模式串最长 35

int n, m;               // n：最终串长度，m：模式串长度
int ne[MAX_PAT];        // KMP 的 next 数组
char pat[MAX_PAT];      // 模式串（1下标）

// 矩阵结构体：竞赛/复试标准写法
struct Matrix {
    ll a[MAX_STATE][MAX_STATE];

    // 初始化全 0
    Matrix() {
        memset(a, 0, sizeof(a));
    }

    // 矩阵乘法
    Matrix operator*(const Matrix &other) const {
        Matrix res;
        for (int i = 0; i < MAX_STATE; i++) {
            for (int k = 0; k < MAX_STATE; k++) {
                if (a[i][k] == 0) continue;  // 小优化，跳过 0
                for (int j = 0; j < MAX_STATE; j++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

// 矩阵快速幂
Matrix matrix_pow(Matrix a, int power) {
    Matrix res;
    // 单位矩阵（对角为 1）
    for (int i = 0; i < MAX_STATE; i++)
        res.a[i][i] = 1;

    while (power > 0) {
        if (power & 1)
            res = res * a;
        a = a * a;
        power >>= 1;
    }
    return res;
}

// 构建状态转移矩阵
void build_trans(Matrix &trans) {
    // 一共 3 层：匹配 0 次、1 次、2 次
    for (int cnt = 0; cnt <= 2; cnt++) {
        // 每层的起始编号
        int base = 1 + cnt * (m + 1);

        // 枚举 KMP 上的位置 j
        for (int j = 0; j < m; j++) {
            int now_id = base + j;

            // 枚举下一个字母 a-z
            for (int c = 0; c < 26; c++) {
                char ch = 'a' + c;
                int cur = j;

                // KMP 跳转到下一个位置
                while (cur && pat[cur + 1] != ch)
                    cur = ne[cur];
                if (pat[cur + 1] == ch)
                    cur++;

                // 如果匹配成功了一次
                if (cur == m) {
                    // 已经匹配 2 次，不能再增加
                    if (cnt >= 2) continue;

                    // 匹配后跳回 next[m]，进入下一层
                    cur = ne[cur];
                    int next_id = 1 + (cnt + 1) * (m + 1) + cur;
                    trans.a[now_id][next_id]++;
                } else {
                    // 没有匹配成功，留在当前层
                    int next_id = base + cur;
                    trans.a[now_id][next_id]++;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 输入模式串（1下标）、长度 n
    cin >> pat + 1 >> n;
    m = strlen(pat + 1);

    // 求 KMP next 数组
    int now = 0;
    for (int i = 2; i <= m; i++) {
        while (now && pat[now + 1] != pat[i])
            now = ne[now];
        if (pat[now + 1] == pat[i])
            now++;
        ne[i] = now;
    }

    // 构建转移矩阵
    Matrix trans;
    build_trans(trans);

    // 初始状态：长度 0，匹配 0 次，位置 0
    Matrix ans;
    ans.a[1][1] = 1;

    // 矩阵快速幂 ^n
    ans = ans * matrix_pow(trans, n);

    // 答案：所有匹配次数 = 2 的状态之和
    ll res = 0;
    int L = 1 + 2 * (m + 1);
    int R = 1 + 3 * (m + 1);
    for (int i = L; i < R; i++) {
        res = (res + ans.a[1][i]) % MOD;
    }

    cout << res << endl;
    return 0;
}