字串变换

形式化题目

给定两个字符串 $A, B$ 和若干条变换规则 $A_i \to B_i$ （ $A$ 、 $B$ 及所有规则串的长度都不超过 $20$ ，规则不超过 $6$ 条）。一次变换是：选定一条规则 $(x \to y)$ ，再选定当前串中 $x$ 的一处出现，把这一处 $x$ 替换成 $y$ ，得到新串。

问至少经过多少次变换能把 $A$ 变成 $B$ 。若在 $10$ 步（含 $10$ 步）内做不到，输出 NO ANSWER!。

正解

思路

第一步：把变换过程看成图上最短路。

每个字符串是一个状态（图的节点）；如果当前串 $s$ 中某条规则的左串 $x$ 在位置 $i$ 出现，把它替换成右串 $y$ 得到 $t$ ，就连一条有向边 $s \to t$ 。每次变换代价为 $1$ ，于是"最少变换次数"就是从 $A$ 到 $B$ 的最短路 —— 边权全为 $1$ ，用 BFS。

扩展一个状态时要做两件事：枚举每条规则；用"从头开始反复 find"找出 $x$ 在 $s$ 中的每一处出现（出现可以重叠，比如规则 aa -> b 作用在 aaa 上，位置 $0$ 和位置 $1$ 是两种不同变换）。 $A = B$ 是平凡情形，直接输出 $0$ 。

第二步：单向 BFS 的瓶颈 —— 分支爆炸。

每个串的出边多达"规则数 $\times$ 出现位置数"，而答案上限是 $10$ 步。最坏情况下单向 BFS 要把深度 $10$ 的整棵搜索树几乎走完，规模随深度指数增长。

第三步：双向 BFS 消除瓶颈。

从 $A$ 和 $B$ 两端同时做 BFS，各自扩展到深度约 $5$ 。深度 $d$ 的搜索规模约为 $k^d$ ，两个 $k^{5}$ 相加远小于一个 $k^{10}$ —— 这就是把指数瓶颈砍半的优化。两端各自维护一张"串 $\to$ 最少到达步数"的哈希表（代码里的 seen_a / seen_b），某侧扩展出新串 $t$ 时，若 $t$ 已出现在对面的表里，说明两棵搜索树接上了：

\text{总步数} = \text{本侧到达深度} + \text{对面到达 } t \text{ 的深度}

三个容易写错的细节：

反向规则：从 $B$ 往回搜时，边的方向要反过来，即使用规则集合 $\{(B_i, A_i)\}$ —— 代码里的 back。
相遇步数要取 min：同一轮扩展可能撞上对面深度不同的多个串，答案取"本侧深度 + 对面相遇点深度"的最小值，不能直接输出当前轮数。
两侧交替扩展：每轮扩展当前层更小的一侧（len(fa) <= len(fb)），让两侧规模尽量平衡；两侧深度之和每轮至多增加 $1$ ，所以循环 $10$ 轮就能覆盖 $1 \sim 10$ 的全部答案；某一侧再也扩不出新串时提前结束，输出 NO ANSWER!。

用官方数据 string5（CmYkRgB123 → 321BgRkYmC，规则 CmYk->321B、RgB1->gRkY、23->mC，答案为 $3$ ）看一下正向三步是如何逼近 $B$ 的：

graph LR
  subgraph forward ["正向：从 A 出发"]
    A0["CmYkRgB123<br/>(0 步)"] -->|"CmYk→321B"| A1["321BRgB123<br/>(1 步)"]
    A1 -->|"RgB1→gRkY"| A2["321BgRkY23<br/>(2 步)"]
  end
  B0["321BgRkYmC<br/>B (反向 0 步)"]
  A2 ==|"第 3 步：规则 23→mC，双向 BFS 在这里相遇"|== B0

正向搜索每一步都只在串的头部附近做替换；第 $3$ 步把结尾的 23 换成 mC 时，恰好得到 $B$ 本身 —— 相当于正向深度 $3$ 的串撞上了反向深度 $0$ 的表，两侧深度之和 $3 + 0 = 3$ 就是答案。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string a, b;
vector<pair<string, string> > rules;
vector<pair<string, string> > back_rules;

// 返回 s 中所有 sub 的出现起点
vector<int> hits(const string& s, const string& sub) {
    vector<int> res;
    size_t i = s.find(sub);
    while (i != string::npos) {
        res.push_back((int)i);
        i = s.find(sub, i + 1);
    }
    return res;
}

// 把 front 这一层向外扩一步，返回 (新一层, 本层相遇点)
void step(map<string, int>& front, map<string, int>& seen, const map<string, int>& other,
          const vector<pair<string, string> >& r, int depth,
          map<string, int>& nxt, vector<string>& meeting) {
    nxt.clear();
    meeting.clear();
    for (map<string, int>::iterator it = front.begin(); it != front.end(); ++it) {
        const string& s = it->first;
        for (size_t ri = 0; ri < r.size(); ri++) {
            const string& sa = r[ri].first;
            const string& sb = r[ri].second;
            vector<int> pos = hits(s, sa);
            for (size_t pi = 0; pi < pos.size(); pi++) {
                int i = pos[pi];
                string t = s.substr(0, i) + sb + s.substr(i + sa.size());
                if (seen.find(t) == seen.end()) {
                    seen[t] = depth;
                    if (other.find(t) != other.end()) meeting.push_back(t);
                    nxt[t] = depth;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> words;
    string w;
    while (cin >> w) words.push_back(w);

    a = words[0];
    b = words[1];
    for (size_t i = 2; i + 1 < words.size(); i += 2) {
        rules.push_back(make_pair(words[i], words[i + 1]));
        back_rules.push_back(make_pair(words[i + 1], words[i]));
    }

    if (a == b) { cout << "0\n"; return 0; }

    map<string, int> fa, fb;
    map<string, int> seen_a, seen_b;
    fa[a] = 0; seen_a[a] = 0;
    fb[b] = 0; seen_b[b] = 0;

    for (int round = 0; round < 10; round++) {
        bool forward = fa.size() <= fb.size();
        map<string, int> nxt;
        vector<string> meeting;
        int side_depth = 0;
        if (forward) {
            int maxd = 0;
            for (map<string, int>::iterator it = seen_a.begin(); it != seen_a.end(); ++it)
                maxd = max(maxd, it->second);
            side_depth = maxd + 1;
            step(fa, seen_a, seen_b, rules, side_depth, nxt, meeting);
            if (!meeting.empty()) {
                int best = 1 << 30;
                for (size_t i = 0; i < meeting.size(); i++) {
                    int v = side_depth + seen_b[meeting[i]];
                    best = min(best, v);
                }
                cout << best << "\n";
                return 0;
            }
            fa = nxt;
        } else {
            int maxd = 0;
            for (map<string, int>::iterator it = seen_b.begin(); it != seen_b.end(); ++it)
                maxd = max(maxd, it->second);
            side_depth = maxd + 1;
            step(fb, seen_b, seen_a, back_rules, side_depth, nxt, meeting);
            if (!meeting.empty()) {
                int best = 1 << 30;
                for (size_t i = 0; i < meeting.size(); i++) {
                    int v = side_depth + seen_a[meeting[i]];
                    best = min(best, v);
                }
                cout << best << "\n";
                return 0;
            }
            fb = nxt;
        }
        if (forward ? fa.empty() : fb.empty()) break;
    }
    cout << "NO ANSWER!\n";
    return 0;
}

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#!/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-02 04:52
# update_at: 2026-10-02 04:52

import sys
from collections.abc import Iterator


def hits(s: str, sub: str) -> Iterator[int]:
    """s 中子串 sub 的所有出现起点（允许重叠出现）。"""
    i = s.find(sub)
    while i != -1:
        yield i
        i = s.find(sub, i + 1)


def step(front: dict[str, int], seen: dict[str, int], other: dict[str, int],
         rules: list[tuple[str, str]]) -> tuple[dict[str, int], list[str]]:
    """把 front 这一整层向外扩一步，返回（新的一层, 本层遇到的相遇点）。

    seen 是本方向"串 -> 到达深度"，other 是对面方向的同一张表；
    新串出现在 other 里说明两侧搜索树接上了，接上处总步数 = 两侧深度之和。
    """
    depth = max(front.values()) + 1  # 本层所有新串的深度相同
    nxt: dict[str, int] = {}
    meeting: list[str] = []
    for s in front:
        for a, b in rules:
            for i in hits(s, a):
                t = s[:i] + b + s[i + len(a):]
                if t not in seen:
                    seen[t] = depth
                    if t in other:  # 对面方向已经到过 t，这是一条相遇边
                        meeting.append(t)
                    nxt[t] = depth
    return nxt, meeting


def solve() -> None:
    words = sys.stdin.read().split()
    a, b, *pair_list = words
    rules = list(zip(pair_list[0::2], pair_list[1::2]))
    back = [(b, a) for a, b in rules]  # 反向规则：从 B 往回变

    if a == b:
        print(0)
        return

    fa: dict[str, int] = {a: 0}  # 正向当前层：串 -> 变换次数
    fb: dict[str, int] = {b: 0}  # 反向当前层
    seen_a = dict(fa)            # 各方向所有到过的串及其深度
    seen_b = dict(fb)
    for _ in range(10):          # 总步数上限 10，两侧深度之和每轮加 1
        forward = len(fa) <= len(fb)  # 总是扩展更小的一层
        if forward:
            fa, meeting = step(fa, seen_a, seen_b, rules)
            side_depth = max(seen_a.values())
        else:
            fb, meeting = step(fb, seen_b, seen_a, back)
            side_depth = max(seen_b.values())
        if meeting:  # 相遇总步数 = 本侧深度 + 对面到达各相遇点的深度，取最小
            print(min(side_depth + seen_b[t] if forward else side_depth + seen_a[t]
                      for t in meeting))
            return
        if not (fa if forward else fb):  # 这一侧扩不出新串，永远接不上了
            break
    print("NO ANSWER!")


if __name__ == "__main__":
    solve()

复杂度

设规则数为 $R \leqslant 6$ ，串长上界为 $L$ （本题不超过 $40$ 左右：原串长 $20$ ，每步至多增长 $\max(|B_i| - |A_i|)$ ），单侧可达状态数为 $S$ 。

时间： $O(S \cdot R \cdot L^2)$ —— 每个状态被扩展一次，每条规则找所有出现位置是 $O(L \cdot |A_i|)$ ，每次替换生成新串是 $O(L)$ 。双向 BFS 把深度从 $10$ 降到约 $5$ ， $S$ 按深度 $5$ 计，这就是相对单向 BFS 的加速来源。官方 8 组数据实测每组约 $0.02$ 秒。
空间： $O(S \cdot L)$ ，两张哈希表存下两端所有到过的串。

标准 C++ 做法同样是（双向）BFS + 哈希去重，本解法与其同阶，只是 Python 常数更大。

总结

把"字符串变换"建模成隐式状态图上的单源最短路，边权为 $1$ ，用 BFS 求解。
答案上限 $10$ 步带来指数级的分支爆炸，用双向 BFS 把两侧深度各压到约 $5$ ：从 $A$ 、 $B$ 两端按层扩展，反向侧使用反置的规则，新串出现在对面哈希表中即相遇，总步数为两侧深度之和（多个相遇点取最小值）。
实现要点：str.find 从上次命中位置之后继续找，枚举包括重叠在内的所有出现位置；两侧各维护"串 $\to$ 深度"字典；每轮扩展较小的一侧； $10$ 轮内无相遇或一侧扩展为空则输出 NO ANSWER!。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7字符串变换问题
`- 建模：字符串 = 状态图节点，一次规则替换 = 权 1 的有向边
   `- 单向 BFS 可行，但深度 10 时分支爆炸
      `- 双向 BFS：从 A、B 两端各分层扩展约 5 层
         |- 反向搜索使用规则 (Bi -> Ai)
         |- 新串撞见对面 seen 表 -> 相遇，步数 = 两侧深度之和（多个相遇点取 min）
         `- 扩满 10 层仍无相遇或一侧扩展为空 -> NO ANSWER!

先看每个节点代表的推理结论，再顺着分支检查它如何导向下一步。图中只保留正文已经说明过的关键关系，不替代正文中的样例推演。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析