字符串匹配

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

把每个字符换成到上一次出现位置的距离,按窗口长度裁剪后做广义 KMP,O(n+m) 数出 s 中与 t 同构的子串。

OJ: roj

题目 ID: 1698

难度:提高

标签:字符串KMP同构匹配python

创建: 2026-10-07 15:48

更新: 2026-10-07 15:48

形式化题目

字符集为 {1,2,…,C}\{1, 2, \dots, C\}。"交换 pp 中任意两个字符的位置"是对整串施加一次字母表上的对换, 反复施加可以生成字母表的任意置换;而交换两个相同字符的位置等于什么都没做。 所以题面的"匹配"就是同构:

q 与 p 匹配  ⟺  ∃ φ:{1,…,C}→{1,…,C} 是双射,使得 qi=φ(pi)  (∀i).q \text{ 与 } p \text{ 匹配} \iff \exists\, \varphi: \{1,\dots,C\} \to \{1,\dots,C\} \text{ 是双射,使得 } q_i = \varphi(p_i)\ \ (\forall i).

给定 s[1..n]s[1..n]、t[1..m]t[1..m](TT 组数据),求出所有 l∈[1,n−m+1]l \in [1, n-m+1] 使得窗口 w=s[l..l+m−1]w = s[l..l+m-1] 与 tt 匹配,输出匹配个数 kk 和这些 ll(升序,下标从 1 开始)。

注意两个边界:m>nm > n 时没有任何窗口,答案为 00(第二行是空行);m=1m = 1 时每个位置都匹配, 因为任意两个单字符之间总能建立双射。

正解

思路

先想清楚"匹配"在比什么。 双射 φ\varphi 只关心"哪些位置上的字符彼此相等", 不关心字符本身叫什么名字。所以我们要给每个串造一个与字母表无关的指纹。

对串 xx 的第 ii 位,定义它到上一次出现同一字符的距离

dx[i]=i−max⁡{ j<i:xj=xi },若这样的 j 不存在则记 0.d_x[i] = i - \max\{\, j < i : x_j = x_i \,\}, \qquad \text{若这样的 } j \text{ 不存在则记 } 0 .

对窗口 s[l..l+m−1]s[l..l+m-1] 的第 kk 位(即 ss 的下标 i=l+k−1i = l+k-1), "它在窗口内有同字符"当且仅当 ds[i]≤k−1d_s[i] \le k-1;若 ds[i]≥kd_s[i] \ge k,说明这个字符在窗口里 是首次出现,那个"同字符"落在窗口外面。于是定义窗口签名

σl(k)={ds[l+k−1],ds[l+k−1]<k,0,ds[l+k−1]≥k,sig[k]={dt[k],dt[k]<k,0,dt[k]≥k.\sigma_l(k) = \begin{cases} d_s[l+k-1], & d_s[l+k-1] < k,\\[2pt] 0, & d_s[l+k-1] \ge k,\end{cases} \qquad \text{sig}[k] = \begin{cases} d_t[k], & d_t[k] < k,\\[2pt] 0, & d_t[k] \ge k.\end{cases}

00 是"窗口内首次出现"的记号,因为 d≥1d \ge 1 恒成立,它不会和真实距离撞车。 模式侧的签名 sig\text{sig} 是静态的:模式永远从自己的第 1 位开始对齐, 第 kk 位参与比较时窗口长度恒为 kk。

命题. 窗口 s[l..l+m−1]s[l..l+m-1] 与 tt 匹配   ⟺  \iff 对一切 k∈[1,m]k \in [1, m] 都有 σl(k)=sig[k]\sigma_l(k) = \text{sig}[k]。

证明. 从左往右扫描建立映射:两边第 kk 位都是"首次出现"时,把这两个字符配成一对; 两边都不是首次出现时,第 kk 位的字符已由它上一次出现的位置确定,σl(k)=sig[k]\sigma_l(k) = \text{sig}[k] 恰好说明"重复指向的位置"也一致,不会与已有配对冲突。所以映射良定义; 两边字符出现次数的分布相同,映射既是单射又是满射,即双射。 反过来,若存在双射 φ\varphi 把窗口映到 tt,则"相等关系"在 φ\varphi 下保持不变, 必然逐位得到 σl(k)=sig[k]\sigma_l(k) = \text{sig}[k]。■\blacksquare

瓶颈在哪? 对每个 ll 逐个比 mm 位是 O(nm)O(nm),n=m=106n = m = 10^6 时不可行。 但上面的判据是"逐位比较、相等就往后走、不等就回退",这正是 KMP 的形状。

关键观察:模式侧静态裁剪,文本侧动态裁剪。 KMP 每一步比较的是 “文本第 ii 位"与"模式第 k=j+1k = j+1 位”(jj 是当前已匹配长度):

  • 模式第 kk 位的窗口永远是它的前 kk 位,sig[k]\text{sig}[k] 与 jj 无关,可以预处理;
  • 文本第 ii 位的窗口是"以 ii 结尾、长度 kk"的那一段,kk 随 jj 变化, 所以文本侧必须用当前的 kk 现算:ds[i]<kd_s[i] < k 取 ds[i]d_s[i],否则取 00。

于是只要把 KMP 的字符比较换成

clip⁡(d,k)={d,d<k,0,d≥k,比较 clip⁡(ds[i], j+1)  =  sig[j+1].\operatorname{clip}(d, k) = \begin{cases} d, & d < k,\\ 0, & d \ge k,\end{cases} \qquad \text{比较 } \operatorname{clip}(d_s[i],\, j+1) \;=\; \text{sig}[j+1].

失配数组的求法一模一样,只是把 tt 自己既当模式又当文本: 比较 tt 的第 i+1i+1 位(按窗口长度 k=j+1k = j+1 现算裁剪)与 sig[k]\text{sig}[k]。 注意 k=1k = 1 时 clip⁡\operatorname{clip} 恒为 00,而 sig[1]=0\text{sig}[1] = 0, 所以"任何单字符都能匹配任何单字符",长度为 2 的前缀的 border 长度恒为 1。

小例子. 样例第一组 s=1 2 1 2 3 2s = 1\,2\,1\,2\,3\,2,t=3 1 3t = 3\,1\,3:

ds=[1,2,2,2,5,2],dt=[1,2,2],sig=[0,0,2]d_s = [1,2,2,2,5,2], \quad d_t = [1,2,2], \quad \text{sig} = [0,0,2]

(sig[1]=0\text{sig}[1] = 0 因为 dt[1]=1≥1d_t[1] = 1 \ge 1;sig[2]=0\text{sig}[2] = 0 因为 dt[2]=2≥2d_t[2] = 2 \ge 2, 模式第 2 位的字符 1 在模式里是首次出现;sig[3]=dt[3]=2\text{sig}[3] = d_t[3] = 2,位置 3 与位置 1 的字符相同。)

ll 窗口 σl\sigma_l 是否匹配
1 1 2 1 (0,0,2)(0,0,2) ✓
2 2 1 2 (0,0,2)(0,0,2) ✓
3 1 2 3 (0,0,0)(0,0,0) ✗
4 2 3 2 (0,0,2)(0,0,2) ✓

得到 k=3k = 3、位置 1,2,41,2,4,与样例输出一致。

答案为什么天然升序? KMP 从左往右扫文本,匹配的结束位置 ii 递增, 起始位置 i−m+1i-m+1 也随之递增,按顺序记录即可,不用排序。

实现要点.

  • 距离数组按"上一次出现位置"递推:d[i]=i−last[x]d[i] = i - last[x] 后令 last[x]=ilast[x] = i; lastlast 的下标是字符值,范围 1..C1..C,每组数据只需清 4(C+1)4(C+1) 字节。
  • 输入最大约 31MB(T=3T = 3,每组两组 10610^6 个整数),用 fread 缓冲逐字符读整数, 避免 getchar/cin 的开销。
  • 输出:先输出 kk 与换行,再按顺序输出每个下标后跟一个空格,最后换行; k=0k = 0 时第二行是空行。

代码

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

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: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;
}

复杂度

  • 时间:每组数据 O(n+m)O(n + m)(KMP 失配指针均摊),总计 O(T(n+m))O(T(n+m))。 实测最慢一组 problem9(T=3T=3,n=m=106n = m = 10^6)热缓存下约 0.06 s, 首次读入 31MB 输入时约 0.45 s,限时 1000 ms。
  • 空间:O(n+m+C)O(n + m + C)。实测峰值内存 23 MB,限 256 MB。
  • Python 版:算法同阶,实测 problem9 约 1.69 s,约为限时的 1.7 倍, 存在 TLE 风险(慢在纯 Python 的逐位循环常数,不是把算法换成了暴力)。 同样的算法在 C++ 里就是上面那份 main.cpp:fread 读入 + 全局数组 + 两个 KMP 循环。

总结

  • 同构匹配 = 相等关系结构的匹配:把"字符叫什么"换成"它上一次出现在哪里", 字母表就被彻底抹掉了,问题退化成"两个距离数组逐位相等"。
  • 裁剪是本题的核心技巧:距离只在"上一次出现位置还在窗口内"时才有意义, 否则必须统一记成 0。模式侧的窗口永远是前缀,所以裁剪是静态的、可以预处理; 文本侧的窗口长度随已匹配长度变化,只能在 KMP 里现算。
  • 判据形状决定算法:一旦把匹配写成"逐位比较、失败回退", 它就和 KMP 完全同形,O(nm)O(nm) 直接降到 O(n+m)O(n+m),连失配数组的求法都只需换掉比较函数。
  • 边界:m>nm > n 输出 0 与空行;m=1m = 1 时每个位置都是答案; 单字符之间的匹配永远成立,这解释了 sig[1]=0\text{sig}[1] = 0 和"长度为 2 的前缀 border 恒为 1"。
  • 输出顺序:KMP 的扫描方向保证下标升序,不需要额外排序。