把每个字符换成到上一次出现位置的距离,按窗口长度裁剪后做广义 KMP,O(n+m) 数出 s 中与 t 同构的子串。
OJ: roj
题目 ID: 1698
难度:提高
标签:字符串KMP同构匹配python
创建: 2026-10-07 15:48
更新: 2026-10-07 15:48
形式化题目
字符集为
给定
注意两个边界:
正解
思路
先想清楚"匹配"在比什么。 双射
对串
对窗口
命题. 窗口
证明. 从左往右扫描建立映射:两边第
瓶颈在哪? 对每个
关键观察:模式侧静态裁剪,文本侧动态裁剪。 KMP 每一步比较的是
“文本第
- 模式第
位的窗口永远是它的前 位, 与 无关,可以预处理; - 文本第
位的窗口是"以 结尾、长度 "的那一段, 随 变化, 所以文本侧必须用当前的 现算: 取 ,否则取 。
于是只要把 KMP 的字符比较换成
失配数组的求法一模一样,只是把
小例子. 样例第一组
(
| 窗口 | 是否匹配 | ||
|---|---|---|---|
| 1 | 1 2 1 | ✓ | |
| 2 | 2 1 2 | ✓ | |
| 3 | 1 2 3 | ✗ | |
| 4 | 2 3 2 | ✓ |
得到
答案为什么天然升序? KMP 从左往右扫文本,匹配的结束位置
实现要点.
- 距离数组按"上一次出现位置"递推:
后令 ; 的下标是字符值,范围 ,每组数据只需清 字节。 - 输入最大约 31MB(
,每组两组 个整数),用 fread缓冲逐字符读整数, 避免getchar/cin的开销。 - 输出:先输出
与换行,再按顺序输出每个下标后跟一个空格,最后换行; 时第二行是空行。
代码
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-10-07 15:48
# update_at: 2026-10-07 15:48
import sys
from collections.abc import Iterator
from itertools import islice
# 同构匹配的判定:dist[i] = i 到「上一次出现同一字符的位置」的距离。
# 比较窗口内第 k 位时按窗口长度 k 裁剪:dist >= k 表示该字符在窗口内是首次出现,统一记 0。
# 模式侧第 k 位的裁剪恒为 k(窗口就是 t 的前 k 位),所以可以静态预处理成 sig[]。
def tokens() -> Iterator[bytes]:
"""逐行读入并顺序吐出 token:单行最长约 7MB,整块 split 会造出数百万个 bytes 对象。"""
for line in sys.stdin.buffer:
yield from line.split()
def distances(nums: Iterator[int], length: int, last: list[int]) -> list[int]:
"""dist[i] = 第 i 个字符到上一次出现位置的距离;last[x] 记录字符 x 最近出现的位置。"""
dist = [0] * (length + 1)
for i, x in enumerate(nums, 1):
dist[i] = i - last[x]
last[x] = i
return dist
def signature(dist: list[int], m: int) -> list[int]:
"""模式侧签名 sig[k]:第 k 位按窗口长度 k 裁剪,窗口内首次出现的字符记 0。"""
return [0] + [dist[k] if dist[k] < k else 0 for k in range(1, m + 1)]
def fail_table(sig: list[int], dist: list[int], m: int) -> list[int]:
"""失配数组 fail[i] = t 的前 i 位在同构意义下的最长真 border 长度。"""
fail = [0] * (m + 1)
j = 0
for i in range(1, m):
k = j + 1
d = dist[i + 1] if dist[i + 1] < k else 0 # 文本侧按当前窗口长度 k 动态裁剪
while j and d != sig[k]:
j = fail[j]
k = j + 1
d = dist[i + 1] if dist[i + 1] < k else 0
if d == sig[k]:
j += 1
fail[i + 1] = j
return fail
def match_starts(text: list[int], sig: list[int], fail: list[int], n: int, m: int) -> list[int]:
"""在 s 的距离数组上跑 KMP,按升序产出所有匹配子串的首位下标。"""
starts: list[int] = []
j = 0
for i in range(1, n + 1):
k = j + 1
d = text[i] if text[i] < k else 0
while j and d != sig[k]:
j = fail[j]
k = j + 1
d = text[i] if text[i] < k else 0
if d == sig[k]:
j += 1
if j == m:
starts.append(i + 1 - m) # 匹配段为 [i-m+1, i]
j = fail[j]
return starts
def solve() -> None:
data = tokens()
T = int(next(data))
charset = int(next(data))
out: list[str] = []
for _ in range(T):
n = int(next(data))
m = int(next(data))
last = [0] * (charset + 1) # last[x] = 字符 x 最近一次出现的位置
s_dist = distances(map(int, islice(data, n)), n, last)
last = [0] * (charset + 1)
t_dist = distances(map(int, islice(data, m)), m, last)
sig = signature(t_dist, m)
starts = match_starts(s_dist, sig, fail_table(sig, t_dist, m), n, m)
out.append(str(len(starts)))
out.append(' '.join(map(str, starts))) # 空答案就是空行,和题面输出格式一致
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-07 15:48
* update_at: 2026-10-07 15:48
*/
// ROJ 1698 字符串匹配
// 题意:s 的子串 w 与 t 匹配 <=> 存在双射 f 把 w 的字符映到 t 的字符上,
// 即 w 与 t 的「相等关系结构」完全一致(哪些位置字符相同)。
// 做法:广义 KMP。把每个位置换成「到上一次出现同一字符的距离」,
// 按窗口长度裁剪后比较,距离超过窗口长度的位置统一记 0(表示窗口内首次出现)。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN = 1000005; // n、m、C 的上界都是 1e6
// 各数组的值域都不超过 1e6,装得下 int,所以大容量数组统一用 int 省内存(不用 ll)
int n, m; // s、t 的长度
int charset; // 字符集大小 C,字符取 1..C
int s_dist[MAXN]; // s_dist[i] = i 到「s 中上一次出现 s[i] 的位置」的距离(没出现过则等于 i)
int t_dist[MAXN]; // t_dist[i] 同理,作用于 t
int t_sig[MAXN]; // t_sig[k] = t_dist[k] 按窗口长度 k 裁剪后的值,模式侧的裁剪是静态的
int fail_[MAXN]; // fail_[i] = t 的前 i 个字符在同构意义下的最长真 border 长度
int last_pos[MAXN]; // last_pos[x] = 字符 x 最近一次出现的位置,按组清零
int answer[MAXN]; // 本组所有匹配位置的首位下标,KMP 保证天然升序
// 输入总量可达 31MB,用自带缓冲的 fread 逐个读整数
static char in_buf[1 << 20];
static int in_len = 0;
static int in_pos = 0;
char next_char() {
if (in_pos == in_len) {
in_len = fread(in_buf, 1, sizeof in_buf, stdin);
in_pos = 0;
if (in_len == 0) return 0;
}
return in_buf[in_pos++];
}
int read_int() {
char c = next_char();
while (c && (c < '0' || c > '9')) c = next_char();
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = next_char();
}
return x;
}
// 把一串字符读成「到上一次出现位置的距离」:dist[i] = i - last[x],并更新 last[x]
void read_dist(int *dist, int len) {
for (int i = 1; i <= len; i++) {
int x = read_int();
dist[i] = i - last_pos[x];
last_pos[x] = i;
}
memset(last_pos, 0, sizeof(int) * (charset + 1)); // 只清字符集用到的范围
}
// 处理一组数据
void work() {
n = read_int();
m = read_int();
read_dist(s_dist, n);
read_dist(t_dist, m);
// 模式侧第 k 位比较时,窗口长度恒为 k,所以裁剪是静态的:
// t_dist[k] >= k 说明 t[k] 在 t 的前 k 位里是首次出现,记 0。
t_sig[0] = 0;
for (int k = 1; k <= m; k++) t_sig[k] = t_dist[k] < k ? t_dist[k] : 0;
// 求失配数组:把 t 自己当文本,文本侧第 i+1 位按窗口长度 j+1 动态裁剪
fail_[1] = 0;
int j = 0;
for (int i = 1; i < m; i++) {
int d = t_dist[i + 1] < j + 1 ? t_dist[i + 1] : 0;
while (j > 0 && d != t_sig[j + 1]) {
j = fail_[j];
d = t_dist[i + 1] < j + 1 ? t_dist[i + 1] : 0;
}
if (d == t_sig[j + 1]) j++;
fail_[i + 1] = j;
}
// 在 s 上匹配:当前已匹配长度 j 时,s 侧第 i 位按窗口长度 j+1 动态裁剪
int cnt = 0;
j = 0;
for (int i = 1; i <= n; i++) {
int d = s_dist[i] < j + 1 ? s_dist[i] : 0;
while (j > 0 && d != t_sig[j + 1]) {
j = fail_[j];
d = s_dist[i] < j + 1 ? s_dist[i] : 0;
}
if (d == t_sig[j + 1]) j++;
if (j == m) {
answer[++cnt] = i + 1 - m; // 匹配段是 [i-m+1, i],首位下标从 1 开始
j = fail_[j];
}
}
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++) printf("%d ", answer[i]);
putchar('\n');
}
int main() {
int T = read_int();
charset = read_int();
for (int tc = 1; tc <= T; tc++) work();
return 0;
}复杂度
- 时间:每组数据
(KMP 失配指针均摊),总计 。 实测最慢一组 problem9(, )热缓存下约 0.06 s, 首次读入 31MB 输入时约 0.45 s,限时 1000 ms。 - 空间:
。实测峰值内存 23 MB,限 256 MB。 - Python 版:算法同阶,实测
problem9约 1.69 s,约为限时的 1.7 倍, 存在 TLE 风险(慢在纯 Python 的逐位循环常数,不是把算法换成了暴力)。 同样的算法在 C++ 里就是上面那份main.cpp:fread读入 + 全局数组 + 两个 KMP 循环。
总结
- 同构匹配 = 相等关系结构的匹配:把"字符叫什么"换成"它上一次出现在哪里", 字母表就被彻底抹掉了,问题退化成"两个距离数组逐位相等"。
- 裁剪是本题的核心技巧:距离只在"上一次出现位置还在窗口内"时才有意义, 否则必须统一记成 0。模式侧的窗口永远是前缀,所以裁剪是静态的、可以预处理; 文本侧的窗口长度随已匹配长度变化,只能在 KMP 里现算。
- 判据形状决定算法:一旦把匹配写成"逐位比较、失败回退",
它就和 KMP 完全同形,
直接降到 ,连失配数组的求法都只需换掉比较函数。 - 边界:
输出 0 与空行; 时每个位置都是答案; 单字符之间的匹配永远成立,这解释了 和"长度为 2 的前缀 border 恒为 1"。 - 输出顺序:KMP 的扫描方向保证下标升序,不需要额外排序。