KMP 字符串匹配（模式串出现次数统计与最短循环节解析）

A-别针少儿编程

33人浏览 · 2026-09-02 07:02:53

A-别针少儿编程 · 2026-09-02 07:02:53 发布

引言

在少儿编程与算法竞赛中，「在一个长文本里找关键词」是最常见的一类问题。比如校园科技节组委会拿到一份上万字的活动报道，想统计某个固定标语、某个选手姓名出现了几次；又比如判断一段指令序列是否由某个最小单元不断循环拼接而成。

如果用「从每个位置暴力尝试匹配」的做法，最坏情况下时间复杂度会达到 O(n×m)，文本一长就会超时。本期我们讲清 KMP 算法——它通过一个巧妙的「前缀函数（next 数组）」，把匹配做到线性的 O(n+m)，并且还能顺便解决「最短循环节」「字符串周期」等进阶问题。

题目 / 项目目标

【原创练习题】关键词检索与周期判定

给定文本串 S（长度 n，仅含小写字母）与模式串 P（长度 m，仅含小写字母）。

第一问（出现次数）：统计 P 作为连续子串在 S 中出现的次数。允许重叠（例如在 "ababab" 中 "abab" 出现了 2 次）。
第二问（最短循环节）：求 P 的最短循环节长度。若 P 可由某个子串 T 完整重复若干次拼成，输出 |T|；否则输出 |P|（即它本身）。

输入格式
第一行：文本串 S
第二行：模式串 P

输出格式
第一行：第一问答案（出现次数）
第二行：第二问答案（最短循环节长度）

样例输入
abababab abab
样例输出
3 2
样例解释："abab" 在 "abababab" 的起始位置 0、2、4 各出现一次（互相重叠），共 3 次；"abab" 由 "ab" 重复 2 次拼成，最短循环节长度为 2。

核心考点

为什么暴力会超时：双层循环，最坏 O(n·m)。
前缀函数 / next 数组的定义：next[i] 表示 P[0..i] 这个前缀里，最长的、同时是真前缀又是真后缀的子串长度（也叫 border 长度）。
next 数组的线性构造：当字符失配时，利用已经算出的 border 信息「回退」，而不是从头再来。
匹配过程的状态机思想：文本指针 i 只前进不回头，模式指针 j 失配时跳到 next[j]，整体只扫描一遍文本。
可重叠计数的关键：每匹配成功一次后，把 j 设为 next[j] 继续匹配，而不是重置为 0。
时间复杂度 O(n+m)、空间复杂度 O(m) 的严格来源。
border 与循环节的关系：P 的最短循环节长度 = m - next[m]（当 m 能被它整除时）。

解法 / 拆解

第一步：构造前缀函数 next

next[i] 的物理意义是「前缀 P[0..i] 的最大 border 长度」。构造时用两个指针 i（当前处理到的位置）和 j（当前 border 长度 / 上一位置的 next 值）：

若 P[i] == P[j]，则 border 可以延长，next[i+1] = j+1；
否则让 j 回退到 next[j]，直到能接上或退到 -1（表示只能从 0 重新开始）。

这个回退过程正是 KMP 高效的核心：它复用了已经比较过的信息，避免把模式串整体往右只挪一格的笨办法。

第二步：用 next 做匹配与计数

文本指针 i 从 0 走到 n-1：

S[i] == P[j] → 两个指针一起前进；
失配 → j = next[j]（可能回退到 -1）；
j == m 说明整段匹配成功：cnt++，随后 j = next[j] 继续（保留已匹配部分，支持重叠计数）。

第三步：最短循环节

由 border 理论，P 存在长度为 L = m - next[m] 的循环节的充要条件是 m % L == 0。否则 P 是「本原串」，最短循环节就是它自己。

C++ 解法

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 构造前缀函数 next：next[i] = P[0..i] 的最长 border 长度
vector<int> buildNext(const string& P) {
    int m = P.size();
    vector<int> nxt(m + 1, 0);
    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;
}

// 第一问：统计 P 在 S 中出现的次数（允许重叠）
int countOcc(const string& S, const string& P) {
    if (P.empty()) return 0;
    vector<int> nxt = buildNext(P);
    int n = S.size(), m = P.size();
    int i = 0, j = 0, cnt = 0;
    while (i < n) {
        if (j == -1 || S[i] == P[j]) {
            ++i; ++j;
        } else {
            j = nxt[j];
        }
        if (j == m) {          // 完整匹配一次
            ++cnt;
            j = nxt[j];        // 关键：回退后继续，支持重叠
        }
    }
    return cnt;
}

// 第二问：最短循环节长度
int minCycle(const string& P) {
    if (P.empty()) return 0;
    vector<int> nxt = buildNext(P);
    int m = P.size();
    int L = m - nxt[m];
    if (m % L == 0) return L;
    return m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S, P;
    getline(cin, S);
    getline(cin, P);
    cout << countOcc(S, P) << "\n";
    cout << minCycle(P) << "\n";
    return 0;
}

Python 解法

def build_next(P):
    m = len(P)
    nxt = [0] * (m + 1)
    nxt[0] = -1
    i = 0
    j = -1
    while i < m:
        if j == -1 or P[i] == P[j]:
            i += 1
            j += 1
            nxt[i] = j
        else:
            j = nxt[j]
    return nxt

def count_occ(S, P):
    if not P:
        return 0
    nxt = build_next(P)
    n, m = len(S), len(P)
    i = j = 0
    cnt = 0
    while i < n:
        if j == -1 or S[i] == P[j]:
            i += 1
            j += 1
        else:
            j = nxt[j]
        if j == m:
            cnt += 1
            j = nxt[j]      # 回退后继续，支持重叠计数
    return cnt

def min_cycle(P):
    if not P:
        return 0
    nxt = build_next(P)
    m = len(P)
    L = m - nxt[m]
    return L if m % L == 0 else m

def main():
    S = input().strip()
    P = input().strip()
    print(count_occ(S, P))
    print(min_cycle(P))

if __name__ == "__main__":
    main()