编码是一个字母对合映射;子串 U 能编码成 T 当且仅当二者模式同构且诱导双射满足对合律,用换比较规则的 KMP 找同构窗口再逐字母验对合。
OJ: roj
题目 ID: 1692
难度:提高+/省选-
标签:字符串KMPpython
创建: 2026-10-07 16:03
更新: 2026-10-07 16:03
形式化题目
先选定若干对互不相交的小写字母对(不相交指每个字母至多出现在一对里),得到一个映射
这样的
给定串
以样例 1(
正解
思路
把编码翻译成约束。 窗口
- 模式同构:
作为双射,意味着 中两个字母相等当且仅当 中对应两位相等。 反过来,只要这条"模式同构"成立,就能定义一个双射 :把每个出现在 中的字母映到 对应位的字母。 - 对合律:
只是双射,未必是对合。还需检查 对每个出现的字母 成立。
这里有个关键细节:
如何判模式同构。 恰好相等用 KMP,模式同构则把"字符相等"换成 prev 编码相等。 prev 编码定义为
也就是"与上一次出现的距离"。它能刻画模式:
于是把
跨窗口的坑。 prev 编码是相对于整串算的,但窗口只截取一段。窗口
一个重要的性质保证了窗口左移不出错:窗口内编码只依赖窗口内的相对结构(是否首次出现、
隔多远),而 KMP 里与模式第
素材源里的
std.cpp走的是另一条路:双 64 位 rolling hash 维护, 利用 “prev 位置 是单射” 这一性质,每次滑动至多修正一位。 本文的 main.cpp与main.py都是按题面自行推导的 KMP 版本,未拄std.cpp; 两套实现已在 10 组随仓数据与 4000 组随机小数据上逐点一致。
如何验对合律。 模式同构一旦成立,双射
于是对合律的检查只需枚举
用样例 1 起点
另外,为什么不直接用哈希。 prev 编码相等可以直接哈希比较,但换窗口时窗口内编码会随左端变化,
需要
如何找首次出现的位置。 预处理
样例 1 逐步追踪。
| 窗口 |
与 |
对合律 | 计入答案 | ||
|---|---|---|---|---|---|
| 1 | abaca |
[0,0,2,0,2] |
✅ | ✅ |
✅ |
| 2 | bacab |
[0,0,0,2,4] |
❌ 第 3 位 | — | ❌ |
| 3 | acaba |
[0,0,2,0,2] |
✅ | ✅ |
✅ |
| 4 | cabad |
[0,0,0,2,0] |
❌ 第 3 位 | — | ❌ |
| 5 | abada |
[0,0,2,0,2] |
✅ | ❌ |
❌ |
| 6 | badab |
[0,0,0,2,4] |
❌ 第 3 位 | — | ❌ |
| 7 | adaba |
[0,0,2,0,2] |
✅ | ✅ |
✅ |
| 8,9 | 长度不足 5 | — | — | — | ❌ |
四个窗口通过了 KMP 的同构检查,但只有 0 vs 2),
第 1 位和第 3 位在
代码
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:42
# update_at: 2026-10-07 15:42
import sys
# 每个字母在 S 中留一个只增不减的游标:游标指向该字母在"当前窗口左端及之后"的
# 首次出现位置。窗口左端单调右移,游标永不回退。
# 窗口 [p, p+m-1] 能编码成 T 的两条判据:模式同构(比较 prev 编码)+ 对合律。
type Occ = dict[str, list[int]] # 字母 -> 在 S 中出现的下标(升序)
type ByLetter = dict[str, int] # 字母 -> 一个位置(最近出现 / 首次出现 / 窗口游标)
type Index = tuple[str, Occ, ByLetter] # (S, 出现位置表, 游标表),判定对合律时一起传
def prev_codes(x: str) -> list[int]:
"""prev 编码:某位字符与它上一次出现的距离,首次出现记 0。"""
last: ByLetter = {}
codes: list[int] = []
for i, c in enumerate(x):
codes.append(i - last.get(c, i)) # 未出现过时 last.get 回退到 i,差为 0
last[c] = i
return codes
def aligned(pat_val: int, text_prev: int, k: int) -> bool:
"""模式串第 k 位的 prev 值能否与"窗口内相对第 k 位"的文本位对齐。
text_prev 超过 k 说明该字符上一次出现在窗口之外,它在窗口内是首次出现,
编码应当取 0;否则窗口内的编码就是 text_prev 本身。
"""
window_code = text_prev if text_prev <= k else 0
return pat_val == window_code
def isomorphic_starts(pv_s: list[int], pv_t: list[int], n: int, m: int) -> list[int]:
"""产出所有与模式串"模式同构"的窗口起点(0-based)。
比较规则换成 prev 编码后,KMP 照常成立:border 表也按同一规则算。
"""
fail = [0] * (m + 1)
k = 0
for j in range(1, m):
while k and not aligned(pv_t[k], pv_t[j], k):
k = fail[k]
if aligned(pv_t[k], pv_t[j], k):
k += 1
fail[j + 1] = k
starts: list[int] = []
k = 0
for i in range(n):
while k and not aligned(pv_t[k], pv_s[i], k):
k = fail[k]
if aligned(pv_t[k], pv_s[i], k):
k += 1
if k == m:
starts.append(i - m + 1)
k = fail[m]
return starts
def involute_ok(p: int, m: int, t: str, first_t: ByLetter, idx: Index) -> bool:
"""窗口 [p, p+m-1] 是否满足对合律(模式同构已经把双射 g 完全定死)。
T 中字母 b 首次出现在第 first_t[b] 位,模式同构迫使 g(S[p+q]) = b;
若 b 也出现在窗口内,则窗口内 b 的首次出现位置 j 必须满足 g(b) = T[j]。
"""
s, occ, curs = idx
right = p + m - 1
for b, q in first_t.items():
positions = occ.get(b)
if positions is None:
continue # b 在 S 中根本不出现,窗内必无
size = len(positions)
c = curs[b]
while c < size and positions[c] < p: # 游标只增不减,均摊 O(1)
c += 1
curs[b] = c
if c == size or positions[c] > right:
continue # b 不在窗口内,对合律不约束它
jb = positions[c] - p # 窗口内 b 首次出现的位置(0-based)
if t[jb] != s[p + q]: # g(b) 应当等于 g^-1 推回的字母 a
return False
return True
def build_index(s: str, t: str) -> tuple[ByLetter, Index]:
"""把两个串物化成对合律检查需要的查表:(T 的首现位置表, 对合律检查状态)。"""
occ: Occ = {}
for i, c in enumerate(s):
occ.setdefault(c, []).append(i)
first_t: ByLetter = {} # T 中每个字母的首次出现位置(0-based)
for j, c in enumerate(t):
first_t.setdefault(c, j)
return first_t, (s, occ, dict.fromkeys(first_t, 0))
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n, m = int(next(data)), int(next(data))
s, t = next(data).decode(), next(data).decode()
first_t, idx = build_index(s, t)
ans = [p + 1 for p in isomorphic_starts(prev_codes(s), prev_codes(t), n, m)
if involute_ok(p, m, t, first_t, idx)]
out = [str(len(ans))]
if ans:
out.append(' '.join(map(str, ans)))
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:42
* update_at: 2026-10-07 15:42
*/
// ROJ 1692 字符串编码
// 题意:选若干对互不相交的小写字母对(每个字母至多出现在一对里),把串中选中字母换成
// 它的配对字母,未选中的字母保持不变——这正好是一个"对合"映射 f(f(f(a)) = a)。
// 求 S 有多少个子串能编码成 T,按升序输出起点(1 起)。
//
// 子串 U 能编码成 T 当且仅当下面两条同时成立:
// (A) 模式同构:存在字母间的双射 g 使 g(U[j]) = T[j]。等价于 U 与 T 的 prev 编码逐位相等
// (prev 编码:某位字符与它上一次出现的距离,首次出现记 0)。
// (B) 对合律:若字母 a 出现在 U 中、g(a) = b 且 b 也出现在 U 中,则必须 g(b) = a。
// 若 b 不出现在 U 中,直接把 a 与 b 配成一对即可,没有额外约束。
// 判定 (A) 用"比较规则换成 prev 编码"的 KMP;判定 (B) 逐字母 O(26) 检查。
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
ll n, m;
char S[MAXN], T[MAXN]; // 1-based,S 是文本串,T 是模式串
ll pvS[MAXN]; // pvS[i] = S[i] 与它上一次出现的距离,首次出现记 0
ll pvT[MAXN]; // pvT[j] 同理,对应 T
ll failArr[MAXN]; // failArr[j] = 模式串前 j 位的"模式同构"最长 border 长度
// 一个字母在 S 中的出现位置,以及一个随窗口左端单调右移的扫描指针
struct LetterPos {
vector<ll> positions; // 升序的出现位置
ll cursor; // positions[cursor] 是该字母在"当前窗口左端及之后"的首次出现
};
LetterPos letterPos[26];
int tLetter[26]; // T 中出现的所有字母(去重,按字母序)
ll tLetterCnt;
ll firstOccT[26]; // T 中每个字母首次出现的位置(1-based),0 表示 T 中不出现
ll ans[MAXN]; // 所有合法子串的起点(升序)
ll ansCnt;
// 模式串第 k+1 位能否与"窗口内相对下标 k+1"的文本位对齐。
// 文本位原始 prev 值为 textPrev:它上一次出现若还在窗口内(textPrev <= k),
// 编码就是 textPrev;否则说明上一次出现在窗口之外,该位在窗口内是首次出现,编码为 0。
bool canAlign(ll patVal, ll textPrev, ll k) {
ll windowCode = textPrev <= k ? textPrev : 0;
return patVal == windowCode;
}
// 判定窗口 [p, p+m-1] 是否满足对合律。
// 模式同构把"窗口字母 -> T 字母"的双射 g 定死了:若字母 b 在 T 中首次出现在第 q 位,
// 则 g(S[p+q-1]) = b(因为 T 第 q 位就是 b)。于是对合律要求:当 b 也出现在窗口内时,
// 窗口内 b 的首次出现位置 jb 必须满足 g(b) = T[jb] 等于 S[p+q-1]。
bool checkInvolve(ll p) {
ll right = p + m - 1;
for (ll idx = 0; idx < tLetterCnt; idx++) {
ll b = tLetter[idx];
vector<ll>& positions = letterPos[b].positions;
ll& cursor = letterPos[b].cursor;
ll cnt = positions.size(); // 出现位置表长度;用 ll 与游标同类型,避免有符号/无符号混比
// 窗口左端单调右移,cursor 只增不减,每个位置最多被跳过一次,均摊 O(n)
while (cursor < cnt && positions[cursor] < p) cursor++;
if (cursor < cnt && positions[cursor] <= right) {
ll jb = positions[cursor] - p + 1; // 字母 b 在窗口内首次出现的位置
if (T[jb] - 'a' != S[p + firstOccT[b] - 1] - 'a') return false;
}
}
return true;
}
int main() {
scanf("%lld %lld", &n, &m);
scanf("%s %s", S + 1, T + 1);
// 建立两个串的 prev 编码,同时把 S 的每个字母的出现位置按字母分桶
ll last[26];
for (int c = 0; c < 26; c++) {
last[c] = 0;
letterPos[c].cursor = 0;
}
for (ll i = 1; i <= n; i++) {
int c = S[i] - 'a';
pvS[i] = last[c] ? i - last[c] : 0;
last[c] = i;
letterPos[c].positions.push_back(i);
}
for (int c = 0; c < 26; c++) last[c] = 0;
for (ll j = 1; j <= m; j++) {
int c = T[j] - 'a';
pvT[j] = last[c] ? j - last[c] : 0;
last[c] = j;
}
// T 中出现的字母表与每个字母的首次出现位置(逆序赋值,留下的就是最小位置)
for (int c = 0; c < 26; c++) firstOccT[c] = 0;
for (ll j = m; j >= 1; j--) firstOccT[T[j] - 'a'] = j;
tLetterCnt = 0;
for (int c = 0; c < 26; c++)
if (firstOccT[c]) tLetter[tLetterCnt++] = c;
// 模式串的 KMP 失配表:比较规则换成 canAlign,因为这里判定的是"模式同构"
failArr[1] = 0;
ll k = 0;
for (ll j = 2; j <= m; j++) {
while (k > 0 && !canAlign(pvT[k + 1], pvT[j], k)) k = failArr[k];
if (canAlign(pvT[k + 1], pvT[j], k)) k++;
failArr[j] = k;
}
// 在 S 上跑 KMP:每匹配到一个长度 m 的窗口,再用对合律筛一次
k = 0;
for (ll i = 1; i <= n; i++) {
while (k > 0 && !canAlign(pvT[k + 1], pvS[i], k)) k = failArr[k];
if (canAlign(pvT[k + 1], pvS[i], k)) k++;
if (k == m) {
ll p = i - m + 1; // 窗口起点
if (checkInvolve(p)) ans[++ansCnt] = p;
k = failArr[m];
}
}
printf("%lld\n", ansCnt);
for (ll i = 1; i <= ansCnt; i++)
printf("%lld%c", ans[i], i == ansCnt ? '\n' : ' ');
return 0;
}复杂度
- 时间:prev 编码与出现位置分桶
,KMP 失配表与匹配各 ; 对每个模式同构窗口做一次对合检查,枚举 中出现过的字母( 个), 每个字母的游标均摊 。总时间 , 最坏 。实测 的极限数据 C++ 约 s。 - 空间:两个 prev 数组、失配数组、每个字母的位置表、答案数组,均为
。 C++ 版实测峰值约 MB;限时 ms、限 MB,余量充足。 - 与 C++ 解法的关系:
main.cpp与main.py是同一算法的两种语言实现, 都用"prev 编码 KMP + 对合律逐字母检查"。Python 版在最大数据上约s, 短时间内不会 TLE;若担心 CPython 常数,可改用 main.cpp。
总结
- 把"编码"还原成映射的结构:字母对互不相交且成对出现,说明这个映射是一个对合
(双射 +
)。整个问题的两条判据就是"双射"(模式同构)与 “ ”(对合律)的翻译。 - 模式同构 ⟺ prev 编码相等:把"字符相等"换成"与上次出现的距离相等", 就能直接用 KMP 扫所有同构窗口,不需要逐窗口建映射。 这是本题最核心的一步转化,也是所有"字符串模式匹配 + 字母重命名"类题目的通用套路。
- 对合律只约束窗口内出现过的字母:
落在窗口外时没有约束, 这一条把检查范围从 个字母精确缩到 中实际出现的字母。 - 单调游标代替二分:窗口左端只增不减,所以每个字母的出现位置表只需一个游标,
均摊
取出"窗口内首次出现",避免了 的二分或 的前缀表。