字符串编码

GitHub跳转原题关系图返回列表

编码是一个字母对合映射;子串 U 能编码成 T 当且仅当二者模式同构且诱导双射满足对合律,用换比较规则的 KMP 找同构窗口再逐字母验对合。

OJ: roj

题目 ID: 1692

难度:提高+/省选-

标签:字符串KMPpython

创建: 2026-10-07 16:03

更新: 2026-10-07 16:03

形式化题目

先选定若干对互不相交的小写字母对(不相交指每个字母至多出现在一对里),得到一个映射 ff:被选中的字母 f(a)=bf(a) = b、f(b)=af(b) = a,未选中的字母 f(a)=af(a) = a。由于字母对互不相交且成对 出现,ff 一定满足

f(f(a))=a(∀a),f 是双射.f(f(a)) = a \quad (\forall a), \qquad f \text{ 是双射}.

这样的 ff 称为一个对合(involution)。编码操作就是把这个 ff 逐字母作用到串上: Tj=f(Uj)T_j = f(U_j)。

给定串 SS(长 nn)与 TT(长 mm),求所有长度恰为 mm 的下标区间 [p,p+m−1][p, p+m-1], 使得存在某个对合 ff 满足 f(S[p+j−1])=Tjf(S[p+j-1]) = T_j(1⩽j⩽m1 \leqslant j \leqslant m)。 输出这样的 pp 的个数与全部取值(升序,下标从 11 开始)。

以样例 1(S=abacabadabaS = \texttt{abacabadaba},T=acabaT = \texttt{acaba})为例,起点 33 对应窗口 acaba\texttt{acaba},取恒等映射 f(a)=a,f(b)=b,f(c)=cf(a)=a, f(b)=b, f(c)=c 即可;起点 11 对应窗口 abaca\texttt{abaca},取字母对 (b,c)(b,c)、其余不变,于是 a→aa \to a、b→cb \to c、c→bc \to b, 正好得到 acaba\texttt{acaba};而起点 55 对应窗口 abada\texttt{abada} 不行——把它变成 acaba\texttt{acaba} 迫使 b→cb \to c、d→bd \to b,双射本身成立(a→aa \to a、b→cb \to c、d→bd \to b 互不相同), 但 d→bd \to b 要求同时有 b→db \to d,与 b→cb \to c 矛盾,对合律被破。

正解

思路

把编码翻译成约束。 窗口 UU 可编码为 TT,等价于存在对合 ff 使 f(Uj)=Tjf(U_j) = T_j。拆成两条:

  1. 模式同构:ff 作为双射,意味着 UU 中两个字母相等当且仅当 TT 中对应两位相等。 反过来,只要这条"模式同构"成立,就能定义一个双射 gg:把每个出现在 UU 中的字母映到 TT 对应位的字母。
  2. 对合律:gg 只是双射,未必是对合。还需检查 g(g(a))=ag(g(a)) = a 对每个出现的字母 aa 成立。

这里有个关键细节:g(a)=bg(a) = b,而 bb 没有出现在 UU 中时,选不选字母对 (a,b)(a,b) 都行—— ff 可以只作用到一个方向上。例如样例 1 起点 11 的窗口 abaca\texttt{abaca} 里只有 a,b,ca, b, c 三个字母,g(b)=cg(b) = c 且 g(c)=bg(c) = b 恰好自洽;但若某个窗口里 gg 把 aa 映到 窗口外的字母 bb 而 bb 不出现,那直接把它们配成一对即可,没有任何冲突。 所以对合律的约束只作用在"aa 与 g(a)g(a) 都出现在窗口中"的字母上。

如何判模式同构。 恰好相等用 KMP,模式同构则把"字符相等"换成 prev 编码相等。 prev 编码定义为

pv(X)i={0,Xi 是首次出现,i−last(Xi),否则,\mathrm{pv}(X)_i = \begin{cases} 0, & X_i \text{ 是首次出现},\\ i - \mathrm{last}(X_i), & \text{否则},\end{cases}

也就是"与上一次出现的距离"。它能刻画模式:XX 与 YY 模式同构当且仅当 pv(X)\mathrm{pv}(X) 与 pv(Y)\mathrm{pv}(Y) 逐位相等。直观上,prev 编码既记录了"这一位是不是首次出现", 又记录了"和上一次出现隔了多远",两串对齐后这些相对结构完全一致,就说明它们的相等/不等 模式完全一致。

于是把 TT 的 prev 编码当模式、SS 的 prev 编码当文本,跑一遍 KMP,就得到所有模式同构的窗口。

跨窗口的坑。 prev 编码是相对于整串算的,但窗口只截取一段。窗口 [p,p+m−1][p, p+m-1] 内第 jj 位(相对下标 jj)的"窗口内 prev 值"是:若 pvS[p+j−1]\mathrm{pvS}[p+j-1] 给出的上一次出现位置仍在窗口内, 就是它本身 pvS[p+j−1]\mathrm{pvS}[p+j-1];若上一次出现落在窗口左边,则该位在窗口内是首次出现, 编码取 00。判据里"上次出现仍在窗口内"恰好等价于 pvS[p+j−1]<j\mathrm{pvS}[p+j-1] < j,所以比较规则写成: 模式串第 kk 位(相对下标 kk)与文本绝对下标 ii 对齐时,文本的窗口内编码是 pvS[i]⩽k−1\mathrm{pvS}[i] \leqslant k - 1 时的 pvS[i]\mathrm{pvS}[i],否则为 00;把它与 pvT[k]\mathrm{pvT}[k] 比较。 KMP 的匹配指针 jj 始终等于"已匹配长度",也就是模式相对下标,套用这个规则正好。

一个重要的性质保证了窗口左移不出错:窗口内编码只依赖窗口内的相对结构(是否首次出现、 隔多远),而 KMP 里与模式第 kk 位比较的文本位总在窗口内的第 kk 位,两边用的是同一个 编码函数,所以失配跳转的正确性不变。

素材源里的 std.cpp 走的是另一条路:双 64 位 rolling hash 维护 ∑jBm−jep(j)\sum_j B^{m-j} e_p(j), 利用 “prev 位置 i−pvS[i]i - \mathrm{pvS}[i] 是单射” 这一性质,每次滑动至多修正一位。 本文的 main.cpp 与 main.py 都是按题面自行推导的 KMP 版本,未拄 std.cpp; 两套实现已在 10 组随仓数据与 4000 组随机小数据上逐点一致。

如何验对合律。 模式同构一旦成立,双射 gg 就被完全定死:由 TT 中字母 bb 的首次出现位置 qbq_b,必有 g(S[p+qb−1])=bg(S[p + q_b - 1]) = b;反过来 UU 中任一字母 aa 的首次出现位置 jaj_a 给出 g(a)=Tjag(a) = T_{j_a}。两种描述是同一件事,只是分别从 TT 和 UU 出发看首次出现。

于是对合律的检查只需枚举 TT 中出现过的字母(不超过 2626 个):对字母 bb,取其首次出现 位置 qbq_b,令 a=S[p+qb−1]a = S[p + q_b - 1] 为窗口内对应位置的字母;若 bb 也出现在窗口 UU 中 (设其窗口内首次出现位置为 jbj_b),则要求 g(b)=Tjbg(b) = T_{j_b} 等于 aa,否则这个窗口不合格。

用样例 1 起点 22 说明模式同构如何拦下它:窗口 bacab\texttt{bacab} 与 acaba\texttt{acaba} 的第 1 位 分别是 bb 与 aa、第 5 位是 bb 与 aa,这两对看着能对调;但第 3 位是 cc 与 aa, 在 bacab\texttt{bacab} 里 cc 是首次出现(编码 00),在 acaba\texttt{acaba} 里第 3 位的 aa 与第 1 位相同 (编码 22)——两边 prev 编码分别为 [0,0,0,2,4][0,0,0,2,4] 与 [0,0,2,0,2][0,0,2,0,2],第 3 位就对不上, 模式同构在第 3 位直接失败。下节末尾的追踪表把每个窗口都列了出来。

另外,为什么不直接用哈希。 prev 编码相等可以直接哈希比较,但换窗口时窗口内编码会随左端变化, 需要 O(1)O(1) 维护。KMP 的路子不需要哈希、也没有碰撞风险, 代价是匹配规则里多一个 pvS[i]<k\mathrm{pvS}[i] < k 的判断;两者复杂度同阶, 本文选 KMP 是因为它代码更短、且不引入任何不确定因素。

如何找首次出现的位置。 预处理 SS 中每个字母的出现位置列表。窗口左端 pp 单调递增, 对每个字母维护一个只增不减的游标,指向"在 pp 及之后"的首次出现位置即可均摊 O(n)O(n)。

样例 1 逐步追踪。 pvT=[0,0,2,0,2]\mathrm{pvT} = [0,0,2,0,2]。对 S=abacabadabaS = \texttt{abacabadaba} 的每个长度 5 窗口,把它单独拿出来重新算一遍"窗口内 prev 编码"(而不是用整串的 prev 编码),就得到下表:

pp 窗口 UU UU 的窗口内 prev 编码 与 pvT\mathrm{pvT} 相等? 对合律 计入答案
1 abaca [0,0,2,0,2] ✅ ✅ g=(b c)g=(b\,c) ✅
2 bacab [0,0,0,2,4] ❌ 第 3 位 — ❌
3 acaba [0,0,2,0,2] ✅ ✅ g=idg=\mathrm{id} ✅
4 cabad [0,0,0,2,0] ❌ 第 3 位 — ❌
5 abada [0,0,2,0,2] ✅ ❌ b↦c, d↦bb \mapsto c,\ d \mapsto b ❌
6 badab [0,0,0,2,4] ❌ 第 3 位 — ❌
7 adaba [0,0,2,0,2] ✅ ✅ g=(d c)g=(d\,c) ✅
8,9 长度不足 5 — — — ❌

四个窗口通过了 KMP 的同构检查,但只有 p∈{1,3,7}p \in \{1,3,7\} 通过了对合律,与样例输出一致。 看失败的 p=5p = 5:窗口 abada\texttt{abada} 与 acaba\texttt{acaba} 同构, 双射被定成 g(a)=ag(a) = a、g(b)=cg(b) = c、g(d)=bg(d) = b。这里 cc 不在窗口内,所以 b↦cb \mapsto c 不受约束; 但 bb 在窗口内(第 2 位),而 g(d)=bg(d) = b,对合律要求 g(b)=dg(b) = d——与 g(b)=cg(b) = c 矛盾, 所以这个窗口不行。这就是为什么同构检查通过后还必须单独验一次对合律。 反例 p=2p = 2 则是在同构阶段就被拦下:第 3 位 prev 编码不同(0 vs 2), 第 1 位和第 3 位在 bacab\texttt{bacab} 里是两个不同字母、在 acaba\texttt{acaba} 里却是同一个字母, 双射不可能成立,KMP 在这一位直接失配。

代码

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-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++ 版(同一算法):

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-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 编码与出现位置分桶 O(n+m)O(n + m),KMP 失配表与匹配各 O(n+m)O(n + m); 对每个模式同构窗口做一次对合检查,枚举 TT 中出现过的字母(⩽26\leqslant 26 个), 每个字母的游标均摊 O(1)O(1)。总时间 O(n+m+26⋅#候选窗口)O(n + m + 26 \cdot \#\text{候选窗口}), 最坏 O(26n)O(26n)。实测 n=m=2×105n = m = 2 \times 10^5 的极限数据 C++ 约 0.020.02 s。
  • 空间:两个 prev 数组、失配数组、每个字母的位置表、答案数组,均为 O(n+m)O(n + m)。 C++ 版实测峰值约 1010 MB;限时 10001000 ms、限 256256 MB,余量充足。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一算法的两种语言实现, 都用"prev 编码 KMP + 对合律逐字母检查"。Python 版在最大数据上约 0.10.1 s, 短时间内不会 TLE;若担心 CPython 常数,可改用 main.cpp。

总结

  • 把"编码"还原成映射的结构:字母对互不相交且成对出现,说明这个映射是一个对合 (双射 + f2=idf^2 = \mathrm{id})。整个问题的两条判据就是"双射"(模式同构)与 “f2=idf^2 = \mathrm{id}”(对合律)的翻译。
  • 模式同构 ⟺ prev 编码相等:把"字符相等"换成"与上次出现的距离相等", 就能直接用 KMP 扫所有同构窗口,不需要逐窗口建映射。 这是本题最核心的一步转化,也是所有"字符串模式匹配 + 字母重命名"类题目的通用套路。
  • 对合律只约束窗口内出现过的字母:g(a)g(a) 落在窗口外时没有约束, 这一条把检查范围从 2626 个字母精确缩到 TT 中实际出现的字母。
  • 单调游标代替二分:窗口左端只增不减,所以每个字母的出现位置表只需一个游标, 均摊 O(1)O(1) 取出"窗口内首次出现",避免了 O(log⁡n)O(\log n) 的二分或 O(26n)O(26n) 的前缀表。