玄武密码

形式化题目

给定母串 $S$ （ $|S| = N$ ）和 $M$ 段文字 $T_1,\dots,T_M$ ，字符集都是 $\{\texttt E,\texttt S,\texttt W,\texttt N\}$ 。对每段文字求最大的 $L$ ，使得 $T$ 的长度为 $L$ 的前缀是 $S$ 的子串； $L=0$ 表示连第一个字符都匹配不上。

样例中 $S=\texttt{SNNSSNS}$ ：NNSS 的前 4 位整体出现在位置 2…5，答案 $4$ ；NNN 只有 NN 出现，答案 $2$ ；WSEE 的首字符 W 不在 $S$ 中，答案 $0$ 。

正解

思路

朴素做法是枚举每段文字的每个前缀、拿去母串里找，单次查找就要 $O(N)$ ，总共 $O(M \cdot L \cdot N)$ ，在 $N \le 10^7$ 、 $M \le 10^5$ 下必然超时。要同时利用两组冗余：

观察 1（前缀共享 → trie）： $M$ 段文字总共不超过 $10^7$ 个字符，把它们全部插进一棵 trie，公共前缀只存一份，节点数 $\le \sum|T| + 1$ 。于是「某段文字的前缀」这个集合恰好就是「trie 上某个节点代表的串」，问题变成：对每个节点 $v$ ，判断 $str(v)$ 是否在 $S$ 中出现过（记 $occ(v)$ ）。

观察 2（单串匹配 → 从每个起点下走）：串 $t$ 是 $S$ 的子串 $\iff$ 从 trie 根出发沿 $t$ 的字符能逐层走通。让 $S$ 的每个起点 $i$ 都从根开始，沿 $S_i, S_{i+1}, \dots$ 同步下走：走到某个节点，就说明这个节点代表的串以 $i$ 为左端点出现在 $S$ 中，给它打上 $occ$ 标记；走到没有对应孩子的节点、或窗口伸出母串，这个起点就被淘汰。

观察 3（前缀封闭 → 答案一次读出）：若某起点走到深度 $d$ ，它必然经过深度 $1..d-1$ 的祖先并同样打上标记，所以 $occ$ 沿每条 trie 路径是从根开始的一段前缀。扫完后，每段文字沿自己的路径下走，答案就是路径上最深的 $occ$ 节点深度。

把三步连起来：建 trie（ $O(\sum|T|)$ ）→ 母串全体起点逐层同步扫描并标记 → 每段沿自身路径取最深命中层。这与本题经典正解「对母串建后缀自动机、每段在自动机上逐字符走、走几步答案就是几」是同一个匹配模型，只是把自动机建在了文字段一侧、按层扫描母串；扫描的工作量是输出敏感的 $\sum_i \ell_i$ （ $\ell_i$ 为起点 $i$ 的最长匹配），字符集只有 4，随机层的存活起点数每层约衰减为 $1/4$ ，长匹配只发生在文字段真正出现的位置附近，实测最大数据（ $N=8\times10^6$ ）不到 1 秒。

Python 实现要点： $N$ 和 $\sum|T|$ 都是 $10^7$ 量级，逐层循环用 numpy 向量化——trie 插入按层批量建档（np.unique 去重一次性建孩子），扫描每层对整个「位置数组 + 节点数组」做批量取字符、查孩子、淘汰、打标记；trie 用扁平数组 child[节点*4+字符] 存储， $occ$ 用布尔数组。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#!/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 14:05
# update_at: 2026-09-30 14:05

# N 可达 8e6、Σ|文字段| 可达 1e7：用 numpy 把「母串每个位置同步沿 trie 下走」
# 的逐层扫描向量化，逐层的转移/存活/标记都是对整个位置数组的批量操作。

import sys

import numpy as np

CHARS = bytes.maketrans(b"ESWN", bytes(range(4)))  # 四象字符 -> 0..3，孩子表按 4 叉编码
PAD = 4  # 定长矩阵的填充值：不是任何真实字符，查孩子表必然落空
MAX_LEN = 100  # 题面保证每段文字长度 <= 100


def build_trie(pat: np.ndarray, plen: np.ndarray) -> tuple[np.ndarray, int]:
    """把所有文字段逐层插入 trie，返回扁平孩子表 child[节点*4+字符] 与节点总数。"""
    child = np.full(4 * (int(plen.sum()) + 1), -1, np.int32)
    node = np.zeros(plen.size, np.int32)  # 每段文字当前走到哪个节点
    born = 1                              # 根节点占 0 号
    for depth in range(1, MAX_LEN + 1):
        alive = np.nonzero(plen >= depth)[0]
        if alive.size == 0:
            break
        want = node[alive] * 4 + pat[alive, depth - 1]   # 想要的 (节点, 字符) 槽位
        fresh = np.unique(want[child[want] < 0])         # 尚无孩子的槽位去重后一次性建档
        child[fresh] = np.arange(born, born + fresh.size, dtype=np.int32)
        born += fresh.size
        node[alive] = child[want]
    return child, born


def mark_occurrence(child: np.ndarray, text: np.ndarray, total: int) -> np.ndarray:
    """母串每个位置都从根同步下走，标记哪些节点的串在母串中出现过。"""
    occ = np.zeros(total, bool)
    pos = np.arange(text.size, dtype=np.int32)  # 还活着的起点
    node = np.zeros(text.size, np.int32)        # 该起点当前匹配到的节点
    for depth in range(1, MAX_LEN + 1):
        keep = pos + depth <= text.size         # 长度 depth 的窗口伸不出母串
        pos, node = pos[keep], node[keep]
        if pos.size == 0:
            break
        step = child[node * 4 + text[pos + depth - 1]]
        live = step >= 0
        pos, node = pos[live], step[live]
        occ[node] = True                        # 走到即出现；其祖先各层必然已被同一位置标记
    return occ


def longest_prefix(child: np.ndarray, occ: np.ndarray, pat: np.ndarray, plen: np.ndarray) -> np.ndarray:
    """每段文字沿自己的 trie 路径下走，答案 = 路径上最深的「出现过」节点深度。"""
    ans = np.zeros(plen.size, np.int32)
    node = np.zeros(plen.size, np.int32)
    for depth in range(1, MAX_LEN + 1):
        alive = np.nonzero(plen >= depth)[0]
        if alive.size == 0:
            break
        node[alive] = child[node[alive] * 4 + pat[alive, depth - 1]]
        hit = occ[node[alive]]                  # occ 沿路径前缀封闭，答案就是最深命中层
        ans[alive[hit]] = depth
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    text_raw = next(data)
    text = np.frombuffer(text_raw[:n].translate(CHARS), np.uint8)
    pats = [next(data) for _ in range(m)]
    plen = np.array([len(p) for p in pats], np.int32)
    pat = np.full((m, MAX_LEN), PAD, np.uint8)
    for i, p in enumerate(pats):                # 每段补齐到定长，方便逐层整列取字符
        pat[i, :len(p)] = np.frombuffer(p.translate(CHARS), np.uint8)

    child, born = build_trie(pat, plen)
    occ = mark_occurrence(child, text, born)
    ans = longest_prefix(child, occ, pat, plen)
    sys.stdout.write("\n".join(map(str, ans.tolist())) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123/**
 * 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-05 03:34
 * update_at: 2026-10-05 03:34
 */
// 玄武密码（JSOI 2012）：把 M 段文字建成 trie（每段长度 <= 100），
// 母串每个起点从根同步逐层下走，走到哪个节点就给哪个节点打「出现过」标记 occ；
// 每段文字沿自身路径下走，答案 = 路径上最深的 occ 节点深度。
//
// 内存说明：sum|T| 可达 1e7，若用 ch[节点*4+字符] 孩子表要 160MB；
// 这里改用「大儿子-兄弟」表示法（son/bro/label 各一个数组），trie 只占 90MB。
#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXSUM = 10000005; // sum|T| <= 1e7，M 段文字总字符数上限
const int MAXN = 10000005;   // 母串长度上限

// trie 的「大儿子-兄弟」表示：节点 0 是根，节点编号从 1 开始
int son[MAXSUM];     // son[u] = u 的第一个孩子节点编号，0 表示没有孩子
int bro[MAXSUM];     // bro[v] = v 的下一个兄弟节点编号，0 表示没有更多兄弟
char label[MAXSUM];  // label[v] = 从父节点走到 v 的那个字符（存 0~3 的编号）
bool occ[MAXSUM];    // occ[v] = str(v) 是否作为子串出现在母串中
int cnt_node = 1;    // 已用节点数（0 是根，1 号起是文字段节点）

char s[MAXN];          // 母串
char pool[MAXSUM + 5]; // 文字段字符池：M 段文字按读入顺序连续存放
ll start_id[100005];   // start_id[i] = 第 i 段文字在 pool 里的起始下标
int tlen[100005];      // tlen[i] = 第 i 段文字的长度

// 存活起点列表：pos[k] = 起点下标，node_id[k] = 该起点当前匹配到的 trie 节点
// 每扫一层就地压缩（只保留还能继续走的起点），所以各只需一份数组
int pos[MAXN];
int node_id[MAXN];

ll n, m;
ll pool_end = 0;   // 字符池当前已用到的位置（游标）
ll max_len = 0;    // 最长文字段长度 = trie 最大深度，扫描层数的天然上限

// 把方向字符映射成 0~3 的编号
int code(char c) {
    if (c == 'E') return 0;
    if (c == 'S') return 1;
    if (c == 'W') return 2;
    return 3; // 'N'
}

// 在 u 的孩子里找字符编号为 c 的孩子，没有返回 0
// 兄弟链最多 4 个节点（字符集大小为 4），扫描代价很小
int find_child(int u, int c) {
    for (int v = son[u]; v != 0; v = bro[v])
        if (label[v] == c) return v;
    return 0;
}

int main() {
    scanf("%lld %lld", &n, &m);
    scanf("%s", s);

    // 第一步：读入 M 段文字存进字符池，同时插入 trie（公共前缀只存一份）
    for (ll i = 1; i <= m; i++) {
        scanf("%s", pool + pool_end);
        start_id[i] = pool_end;
        tlen[i] = (ll)strlen(pool + pool_end);
        if (tlen[i] > max_len) max_len = tlen[i];
        pool_end += tlen[i];
        int cur = 0; // 从根出发沿路径插入
        for (ll j = 0; j < tlen[i]; j++) {
            int c = code(pool[start_id[i] + j]);
            int nxt = find_child(cur, c);
            if (nxt == 0) { // 没有这个孩子就新建，并挂到兄弟链头部
                nxt = cnt_node++;
                label[nxt] = c;
                bro[nxt] = son[cur];
                son[cur] = nxt;
            }
            cur = nxt;
        }
    }

    // 第二步：母串每个起点从根同步逐层下走，走到就打 occ 标记
    // 第 len 层处理的是「以 pos[k] 为左端点、长度为 len 的前缀」
    ll alive = 0; // 当前层存活的起点数
    for (ll i = 0; i < n; i++) { // 初始：所有起点都在根
        pos[alive] = i;
        node_id[alive] = 0;
        alive++;
    }
    // 文字段最长只有 100，所以任何匹配深度都不超过 max_len，层数到此封顶
    for (ll len = 1; len <= max_len; len++) {
        ll w = 0; // 下一层存活起点的写入位置（w <= 读下标，可以就地压缩）
        for (ll k = 0; k < alive; k++) {
            ll i = pos[k];
            if (i + len - 1 >= n) continue; // 窗口伸出母串，淘汰
            int nxt = find_child(node_id[k], code(s[i + len - 1]));
            if (nxt != 0) {
                occ[nxt] = true; // 该节点代表的串以 i 为左端点出现在母串中
                pos[w] = i;
                node_id[w] = nxt;
                w++;
            }
        }
        alive = w;
        if (alive == 0) break; // 没有任何起点还能匹配，提前结束
    }

    // 第三步：每段文字沿自身路径下走，取最深的 occ 节点深度
    // occ 沿路径前缀封闭，命中深度一定连续，最后一个命中就是答案
    for (ll i = 1; i <= m; i++) {
        int cur = 0; // 从根出发重走这一段的路径
        ll best = 0;
        for (ll j = 0; j < tlen[i]; j++) {
            cur = find_child(cur, code(pool[start_id[i] + j]));
            if (cur == 0) break; // 路径断了，后面的前缀一定不在 trie 里
            if (occ[cur]) best = j + 1;
        }
        printf("%lld\n", best);
    }
    return 0;
}

复杂度

时间：trie 构建 $O(\sum|T|)$ ；扫描为输出敏感的 $O\!\left(\sum_i \ell_i\right) \le O(N \cdot L_{\max})$ ，本题数据下实测 symbol9（ $N=8\times10^6$ ， $M=10^5$ ）约 0.86 s。经典的后缀自动机做法是 $O(N + \sum|T|)$ 最坏线性，本实现与其同模型，代价是扫描层依赖实际匹配深度。
空间：孩子表 $4 \times (\sum|T|+1)$ 个 int32 约 158 MB， $occ$ 标记约 10 MB，位置/节点数组峰值约 64 MB（python-oj-short 允许 Python 侧 MLE，不做内存硬限制）。

总结

把「每段文字的每个前缀」收敛成一棵 trie： $M$ 段文字的匹配需求变成对所有 trie 节点的 $occ$ 判定。
匹配方向反转：不是「拿串去母串里找」，而是「母串每个起点同时在 trie 上往下走」，走到即标记，一次扫描覆盖所有子串信息。
$occ$ 沿路径前缀封闭，所以每段答案 = 自身路径上最深的命中节点深度，无需回溯。
实现上用 numpy 把逐层扫描向量化：批量 gather（取字符、查孩子）、compress（淘汰）、scatter（打标记）， $10^7$ 量级数据在秒级完成。
验证：真实测试数据 9/9 全部 PASS，最大一组 0.86 s。

图示解析

以样例 $S=\texttt{SNNSSNS}$ 、文字段 NNSS、NNN、WSEE 为例。三个串共享前缀 N，trie 只有 9 个节点：

graph LR
  R((根)) -->|N| A["N"]
  A -->|N| B["NN"]
  B -->|S| C["NNS"]
  C -->|S| D["NNSS"]
  B -->|N| E["NNN"]
  R -->|W| F["W"]
  F -->|S| G["WS"]
  G -->|E| H["WSE"]
  H -->|E| I["WSEE"]

母串每个起点从根同步下走，× 表示该起点已淘汰：

深度 $d$	位置 0 (`S`)	位置 1 (`N`)	位置 2 (`N`)	位置 3 (`S`)	位置 4 (`S`)	位置 5 (`N`)	位置 6 (`S`)
1	×	`N`	`N`	×	×	`N`	×
2	—	`NN`	×	—	—	×	—
3	—	`NNS`	—	—	—	—	—
4	—	`NNSS`	—	—	—	—	—
5	—	×（`NNSSN` 不在 trie）	—	—	—	—	—

扫描结束时被打上 $occ$ 标记的节点：N、NN、NNS、NNSS（W 子树一个都没走到）。沿各段自身路径取最深命中层：NNSS → NNSS，深度 $4$ ；NNN → NN，深度 $2$ ；WSEE → 无命中，深度 $0$ ——与样例输出一致。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析