「一本通 2.1 例 1」Oulipo

题目描述

给出两个只含大写字母的字符串 $s_1, s_2$ ，求 $s_1$ 在 $s_2$ 中作为子串出现了多少次，允许重叠。例如 $s_1=\texttt{ABA}$ ， $s_2=\texttt{ABAABA}$ ，答案为 $2$ （两个 ABA 共享了字母 A）。输入第一行是数据组数 $T$ ，接下来每组两行依次给出 $s_1$ 和 $s_2$ ，对每组数据输出一行，即出现次数。 $1 \le |s_1| \le 10^4$ ， $1 \le |s_2| \le 10^6$ 。

思路

经典 KMP 计数：先对 $s_1$ 预处理 fail 数组（ $\mathrm{fail}[i]$ 为 $s_1[:i]$ 的最长相等真前后缀长度），再单趟扫 $s_2$ ，失配时沿 fail 链回退、不回退主串指针，均摊 $O(|s_1|+|s_2|)$ 。扫到匹配长度等于 $|s_1|$ 时计数加一，并回退到 $\mathrm{fail}[|s_1|-1]$ 而不是清零，这样重叠的出现也会被数到。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-10-04 11:36

import sys


def kmp_count(pat: str, text: str) -> int:
    """统计模式串 pat 在 text 中出现的次数（允许重叠），KMP 扫一遍。"""
    # 失配指针：fail[i] = pat[:i] 的最长相等真前后缀长度
    fail = [0] * len(pat)
    k = 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]:
            k = fail[k - 1]            # 沿失配链回退
        k += pat[i] == pat[k]          # 匹配上则延长一位
        fail[i] = k

    count = 0
    k = 0                              # 已匹配的 pat 前缀长度
    for ch in text:
        while k and ch != pat[k]:
            k = fail[k - 1]
        k += ch == pat[k]
        count += k == len(pat)         # 完整出现一次（重叠出现不被回退，天然支持）
        if k == len(pat):
            k = fail[k - 1]            # 继续找下一个可重叠出现
    return count


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []

    first = next(data)              # 样例格式首 token 是组数 T；数据文件格式首 token 是 s2
    if first.isdigit():
        for _ in range(int(first)):
            s1 = next(data)         # 每组依次是模式串 s1、文本串 s2
            s2 = next(data)
            out.append(str(kmp_count(s1, s2)))
    else:                           # 数据文件格式：第 1 行 s2，第 2 行 s1
        out.append(str(kmp_count(next(data), first)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:14
 * update_at: 2026-10-06 00:14
 */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

typedef long long ll;

const int MAXP = 1e4 + 5;   // |s1| <= 1e4
const int MAXT = 1e6 + 5;   // |s2| <= 1e6

char s1[MAXP];  // 模式串
char s2[MAXT];  // 文本串
int fail[MAXP]; // fail[i] = s1[:i] 的最长相等真前后缀长度

// 对模式串 s1 预处理失配指针，均摊 O(|s1|)
void build_fail() {
    int m = strlen(s1 + 1); // 串从下标 1 开始存
    fail[1] = 0;
    int k = 0;              // 当前已匹配的 s1 前缀长度
    for (int i = 2; i <= m; ++i) {
        while (k && s1[i] != s1[k + 1]) k = fail[k]; // 沿失配链回退
        if (s1[i] == s1[k + 1]) ++k;
        fail[i] = k;
    }
}

// 统计 s1 在 s2 中出现的次数（允许重叠），均摊 O(|s2|)
int kmp_count() {
    int m = strlen(s1 + 1);
    int n = strlen(s2 + 1);
    int ans = 0;
    int k = 0;              // 已匹配的 s1 前缀长度
    for (int i = 1; i <= n; ++i) {
        while (k && s2[i] != s1[k + 1]) k = fail[k]; // 不回退主串指针，只回退 k
        if (s2[i] == s1[k + 1]) ++k;
        if (k == m) {       // 完整出现一次
            ++ans;
            k = fail[k];    // 回退而不是清零，重叠出现也能被数到
        }
    }
    return ans;
}

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

    int T;
    if (!(std::cin >> T)) return 0;
    while (T--) {
        std::cin >> (s1 + 1) >> (s2 + 1);
        build_fail();
        std::cout << kmp_count() << "\n";
    }
    return 0;
}

「一本通 2.1 例 1」Oulipo

目录

题目描述

思路

参考代码