用 KMP 匹配模式串，每次匹配成功立即计数并清零匹配指针，保证子串互不重叠。
OJ: roj
题目 ID: 1465
难度:普及-
标签:字符串KMP贪心
创建: 2026-09-30 12:30
更新: 2026-10-06 00:19
题目描述
输入多组测试数据，每组一行，由空格分开的主串和模式串。求主串中最多能剪出多少个互不重叠的完整模式串。输入中单独一行 # 表示结束（字符串内部或开头的 # 不算结束）。
数据范围：字符串长度 ≤ 1000。
思路
从左到右扫描主串，用 KMP 匹配模式串；一旦完整匹配成功，答案加 1 并把匹配指针清零，确保剪出的子串互不重叠。
参考代码
Python 版：
python
#!/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-09-30 12:31
# update_at: 2026-09-30 12:31
import sys
def count_non_overlapping(text: str, pattern: str) -> int:
"""计算模式串在主串中互不重叠出现的最大次数（KMP 匹配与贪心跳跃）。"""
m = len(pattern)
pi = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
j += pattern[i] == pattern[j]
pi[i] = j
ans = 0
j = 0
for ch in text:
while j > 0 and ch != pattern[j]:
j = pi[j - 1]
j += ch == pattern[j]
if j == m:
ans += 1
j = 0 # 剪下饰条后不可重叠，重置匹配进度
return ans
def solve() -> None:
lines = sys.stdin.read().splitlines()
out: list[str] = []
for line in lines:
if line == "#":
break
parts = line.split()
if not parts:
continue
text, pattern = parts[0], parts[1]
out.append(str(count_non_overlapping(text, pattern)))
print("\n".join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:19
* update_at: 2026-10-06 00:19
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXL = 1010; // 字符串最大长度
char s[MAXL], t[MAXL]; // s 为主串，t 为模式串
int nxt[MAXL]; // nxt[i] 表示模式串前缀 t[0..i] 的最长相等真前后缀长度
// 预处理模式串 t 的 nxt（前缀函数）数组
void get_next(char t[], int m) {
int j = 0;
nxt[0] = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && t[i] != t[j]) j = nxt[j - 1];
if (t[i] == t[j]) j++;
nxt[i] = j;
}
}
// KMP 匹配，每匹配到一个完整 t 就计数并将匹配指针清零，保证剪出的子串互不重叠
int kmp_count(char s[], int n, char t[], int m) {
int j = 0, ans = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && s[i] != t[j]) j = nxt[j - 1];
if (s[i] == t[j]) j++;
if (j == m) {
ans++;
j = 0; // 剪下这一段，从下一字符重新匹配
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> s) {
if (s[0] == '#' && s[1] == '\0') break; // 单独一个 # 结束输入
cin >> t;
int n = strlen(s);
int m = strlen(t);
get_next(t, m);
cout << kmp_count(s, n, t, m) << "\n";
}
return 0;
}