应急故障修复系统replace补题：AC自动机反转匹配与贪心覆盖详解

这份 U652449 应急故障修复系统（replace）补题报告，我拖了两周才写完。比赛时看到“应急故障修复系统”这个名字，我以为是模拟题，等看到题面里的 replace 又觉得是字符串替换签到题，结果 TLE 了整整四发。下来之后对着样例和残存的比赛记录，把题面一点点还原出来，才发现这题的核心根本不在“替换”本身，而在于“匹配之后怎么决定到底替换哪一段”。如果你也在补这道题，或者在做 AC 自动机相关的字符串问题，这篇报告应该能帮你少走两三个小时的弯路。

1. 题意还原：这道题里的 replace 到底有多少隐藏规则

1.1 凭赛后记录还原的题面

U652449 这套题给的背景名字叫“应急故障修复系统”，用户输入的项目标题里也明确写了 replace，按我赛后恢复出的题面，大致是这样的：

系统维护一条长度为 N 的文本 S，同时有 K 条修复规则，每条规则形如 (Pi, Ri)，意思是一旦检测到故障片段 Pi，就把它修复成 Ri。系统执行规则时，会从左到右扫描整条文本。如果在某个位置 pos 能匹配到至少一条规则的 Pi，那就必须以这个位置为起点进行一次修复。修复完成后，被修复片段覆盖的字符不再参与其他修复，系统不会对刚替换进去的内容做二次匹配。输出最终修复完的整条文本。

这句话看起来很简单，但真正的坑藏在细节里。根据我手头还原出的样例行为，题目还隐含了三条规则：

1. 同一个字符最多只能属于一次修复，也就是替换区间不能重叠。
2. 如果同一个起点能匹配多个 Pi，必须选最长的那条模式串。这样“修复最彻底”，不存在只修一半的情况。
3. 修复完的结果不会继续参与匹配，也就是说不会出现 A 替换成 B、B 又匹配上 C 的递归情况。

数据范围我当时没有完整记下来，但按比赛时的内存和时间限制推断，大致是 N 可以到 10^6 量级，K 到 10^5 量级，所有模式串长度之和在 2×10^5 以内，修复串长度之和也在类似量级。凡是能支撑这种范围的字符串算法，基本就是在往多模式匹配方向逼。

1.2 三条规则为什么每一条都在排除暴力解

先说“字符只能被修复一次”。如果允许区间随意重叠，那问题反而简单——把每条规则的可匹配区间全部求出来，按一定顺序直接替换即可。但一旦要求“一个字符只能属于一个替换”，所有匹配之间立刻产生了竞争：两个区间重叠，选谁不选谁，必须有一个全局决策顺序。

再说“从左到右，最左匹配优先”。这个规则直接否决了“把所有匹配全部找出来再排序”的松弛做法。如果从右往左处理，或者按区间长度排序处理，出来的结果很可能不是题目要的答案。题目要求的是模拟一次从左到右的扫描过程：能匹配就匹配，匹配了就吃掉一整段，然后继续看后面的位置。

最后是“选最长模式串”。这条最有意思。很多人在赛后会写成“对每个匹配串，只要它是模式串就作为候选”，然后会发现同样的起点可能搜出一堆长度不同的模式串。到底选哪个？题目明确说选最长。为什么不是“第一个匹配到的”？因为 AC 自动机在文本上跑的时候，你顺着字符一路往下走，第一个到达的终止节点往往不是最长匹配。

举个例子：S = "aaaa"，模式串有 "aaa" 和 "aa"。如果匹配过程中遇到 "aa" 就立即记录，那起点 0 会被记成长度 2，但实际上这里能匹配到更长的 "aaa"，按题目规则必须选长度 3。这也是很多人第一版贪心代码的典型错误来源。

所以我补题时做的第一件事，不是急着敲 AC 自动机板子，而是先把这三条规则的决策顺序理清楚：先确定起点，最左优先，然后在该起点能用到的所有模式串里选最长，最后整个区间被占用，后续匹配不允许侵入。

2. 一个反例告诉你：按“结束位置”收集匹配为什么必挂

2.1 AC 自动机的天然输出是“以 i 结尾的匹配”

写过 AC 自动机的人都知道，扫描文本 S 时，走到第 i 个字符，自动机里的状态表示的是“以 S[i] 结尾的最长后缀状态”。如果我们提前在 Trie 节点上挂好模式串信息，那顺手取到的匹配都是“以当前位置 i 作为匹配右端点”的匹配。这个特性非常适合处理“以某个字符结尾匹配到了什么”，但不适合处理“以某个位置作为起点开始匹配”。

题目要的决策顺序却是按起点来的：哪个起点靠左，谁先拥有优先权。所以如果直接拿 AC 自动机从左到右跑一遍，把所有“以 i 结尾的匹配”收集起来，再去做区间决策，十有八九会漏掉本该出现的短匹配。

2.2 被丢弃的短匹配可能在后面“复活”

这句话听起来抽象，我直接给一个构造出来的反例，这道题我就在这上面栽过。假设文本 S = "ababa"，规则是：

• "aba" -> X
• "ba" -> Y

正确做法：从左到右扫描。起点 0 匹配到 "aba"，覆盖 S[0..2]，输出 X。然后起点 3 匹配到 "ba"，覆盖 S[3..4]，输出 Y。最后结果是 "XY"。

现在用“每个右端点只保留最长匹配”的方式收集候选。跑 AC 自动机，在位置 2 会匹配到 "aba"，记下一个候选 [0, 3)（左闭右开，下面统一用这个写法避免歧义）。在位置 4 会匹配到 "aba"，记下候选 [2, 5)，同时位置 4 也匹配到了 "ba"，候选 [3, 5)。但因为我们在节点上只保留最长匹配，[3, 5) 这个短候选被丢掉了。接下来做区间决策：候选 [0, 3) 最左，选它没问题。第二个候选是 [2, 5)，它和 [0, 3) 有重叠（位置 2 已经被占用），被拒绝。扫描到位置 3 时发现没有候选信息了，最后两个字符只能原样输出 "ba"。最终结果变成 "Xba"，和正确答案 "XY" 不一致。

问题就出在：位置 3 开头的短匹配 "ba" 和位置 2 开头的最长匹配 "aba" 在同一个右端点 4 结束，AC 自动机的 bestLen 策略只留下了 "aba"，把真正可以作为后续替换的 "ba" 丢了。这个反例也说明，这道题不能简单套“每个右端点记一条最长匹配”的板子。

反过来想，题目需要的信息本质上是“每个起点能匹配到的最长模式串”，而不是“每个右端点匹配到了什么”。既然 AC 自动机天然给的右端点信息，那就想办法把起点和终点互换——反转文本和模式串。

3. 反转文本再匹配：把“从谁开始”换成“以谁结尾”

3.1 反转映射的坐标推算

把原文本 S 反转得到 R，也就是 R[j] = S[N-1-j]。对于每个模式串 Pi，也把它反转成 rev(Pi)。如果原文本里 Pi 出现在起点 pos，覆盖区间 [pos, pos+len)，那么在反转文本里，rev(Pi) 必然也出现一次，并且它的右端点是 e = N-1-pos。反过来，如果反转文本里某个 rev(Pi) 的匹配右端点是 e，那它对应原文本的起点就是 pos = N-1-e。

这组坐标关系是整个解法的地基。

比如 S = "ababa"，N = 5，R = "ababa"。原起点 pos=0 的 "aba" 在 R 里是 "aba"，右端点 4；N-1-4=0，对得上。原起点 pos=3 的 "ba" 反转成 "ab"，在 R 里出现在 R[0..1]，右端点 1；N-1-1=3，也对得上。

关键点来了：所有从同一个原起点 pos 出发的模式串，反转之后在 R 里的右端点统统都是 e = N-1-pos。所以“同一原起点选最长模式串”这个要求，在反转世界里变成了“同一右端点选最长的反转模式串”，而这恰好是 AC 自动机在节点上维护 bestLen 就能一次搞定的事情。

3.2 为什么每个起点只留最长候选就够

那短匹配会不会又一次被丢掉？不会，因为题目规则里“同起点选最长”是强制要求。可以做这样的推理：

如果起点 pos 选的长度是 len_long，某个更短的匹配 len_short 和它同起点。当我们在原文本里从左到右扫描到 pos 时，如果 pos 还没被之前选中的区间覆盖，那就必须选最长匹配，短匹配没有出场机会。如果 pos 已经被之前选中的某个更左区间覆盖，那不管是长匹配还是短匹配，它的起点都已经失效，两者都不会被选中。换句话说，短匹配在“长匹配能用”时不该用，在“长匹配不能用”时也没资格用。所以每个起点只需要保留一个最长候选，这个做法不仅是简化，而且和题目语义完全一致。

3.3 线性扫描的贪心流程

有了“每个原起点 pos 的最长匹配长度 matchLen[pos]”和对应的规则编号 matchId[pos] 之后，重构答案就变成了一次线性扫描：

• 维护一个指针 pos 和当前已覆盖到的右边界 covered。
• 如果 pos 已经被之前替换覆盖，直接跳过，不输出任何字符。
• 如果 pos 没有被覆盖，并且 matchLen[pos] > 0，就把对应的修复串加入答案，然后把 covered 更新为 pos + matchLen[pos]，pos 跳到覆盖区间的末尾。
• 否则原样输出 S[pos]，pos 加 1。

这个贪心看起来简单，但它依赖一个事实：我们始终从左往右处理，一旦走到 pos，说明比 pos 更左的位置都已经决策完毕。此时 pos 能匹配到的最长模式串必须被选中，因为它满足“最左优先”的最高优先级。选中后即使它覆盖了后面一些匹配的起点，那也是题目规则允许的。我曾经想过用区间调度、最大不相交区间之类的复杂思路，后来发现这道题根本不需要，线性扫描就是最贴合题意的做法。

4. 主要实现与代码注释

4.1 数据结构与 build 的细节

我用的是数组版 Trie，节点数开成所有模式串长度之和加 5。每个节点维护 next 数组、fail 指针，以及 bestLen 和 bestId。bestLen 表示“如果自动机停在当前节点，沿 fail 链能遇到的最长模式串长度”，bestId 是对应规则编号。

插入模式串时，我先把它反转，再插进 Trie。为什么反转？因为我们要在反转文本 R 上做匹配，匹配到的右端点对应的是原起点。有一点要特别注意：如果同一个 Trie 节点被多个模式串共享，取其中最长的存到 bestLen。长度相同时，我保留先插入的那个，避免行为不确定。

build 函数里有一个经典优化：把不存在的转移直接指向 fail 节点的转移。这样匹配时不需要 while 循环反复跳 fail，代码会简洁很多，速度也更快。

#include <bits/stdc++.h> using namespace std; const int MAXS = 1000000 + 5; const int SIG = 26; struct Node { int nxt[SIG]; int fail; int bestLen, bestId; Node() { memset(nxt, -1, sizeof(nxt)); fail = 0; bestLen = 0; bestId = -1; } }; vector<Node> trie; int matchLen[MAXS], matchId[MAXS]; vector<string> repairList; void insertPattern(const string& p, int id) { int u = 0; for (char c : p) { int x = c - 'a'; if (trie[u].nxt[x] == -1) { trie[u].nxt[x] = (int)trie.size(); trie.emplace_back(); } u = trie[u].nxt[x]; } if ((int)p.size() > trie[u].bestLen) { trie[u].bestLen = (int)p.size(); trie[u].bestId = id; } } void buildAC() { queue<int> q; for (int c = 0; c < SIG; ++c) { int v = trie[0].nxt[c]; if (v == -1) trie[0].nxt[c] = 0; else { trie[v].fail = 0; q.push(v); } } while (!q.empty()) { int u = q.front(); q.pop(); int f = trie[u].fail; if (trie[f].bestLen > trie[u].bestLen) { trie[u].bestLen = trie[f].bestLen; trie[u].bestId = trie[f].bestId; } for (int c = 0; c < SIG; ++c) { int v = trie[u].nxt[c]; if (v == -1) { trie[u].nxt[c] = trie[trie[u].fail].nxt[c]; } else { trie[v].fail = trie[trie[u].fail].nxt[c]; q.push(v); } } } }

4.2 匹配与重构主流程

匹配阶段直接对反转文本 R 跑自动机，走到右端点 r 时，取节点上的 bestLen。如果大于 0，说明有一个长度为 bestLen 的原始模式串在原文本的 pos = N-1-r 处作为起点出现过。记录到 matchLen[pos] 和 matchId[pos]。

这里我加了一个if (len > matchLen[pos])的判断。因为是不同右端点 r 会映射到不同 pos，理论上一个 pos 只会被访问一次，所以这个判断通常不会触发。但写上的话，即使题目数据里出现异常情况，也不会覆盖成错误信息。

int main() { ios::sync_with_stdio(false); cin.tie(0); string S; cin >> S; int K; cin >> K; trie.emplace_back(); vector<string> patternList; int totalPatternLen = 0; for (int i = 0; i < K; ++i) { string p, r; cin >> p >> r; patternList.push_back(p); repairList.push_back(r); if (p.empty()) continue; reverse(p.begin(), p.end()); insertPattern(p, i); totalPatternLen += (int)p.size(); } string R = S; reverse(R.begin(), R.end()); buildAC(); int n = (int)S.size(); int u = 0; for (int r = 0; r < n; ++r) { u = trie[u].nxt[R[r] - 'a']; if (trie[u].bestLen > 0) { int len = trie[u].bestLen; int id = trie[u].bestId; int pos = n - 1 - r; if (len > matchLen[pos]) { matchLen[pos] = len; matchId[pos] = id; } } } string ans; ans.reserve(n + totalPatternLen); int pos = 0; int covered = 0; while (pos < n) { if (pos < covered) { ++pos; continue; } if (matchLen[pos] > 0) { int len = matchLen[pos]; ans += repairList[matchId[pos]]; covered = pos + len; pos += len; } else { ans += S[pos]; ++pos; } } cout << ans << '\n'; return 0; }

4.3 复杂度说明

构建 Trie 和 fail 指针的复杂度是 O(所有模式串长度之和)，字符集大小在这里是常数 26。扫描反转文本的复杂度是 O(N)。最后重构答案的扫描也是 O(N)。修复串直接拼接到 string 里，总输出长度不超过 N 加上所有修复串长度之和。整个算法是严格的线性复杂度，在 N 到 10^6、模式串总量 2×10^5 的范围内完全够用。

如果你把这段代码交到评测机上，注意建 Trie 之前要先trie.emplace_back()把根节点建出来，不然 insert 第一次访问trie[0]就会越界，这个错很隐蔽。

5. 补题过程中的四个翻车点

5.1 根节点孩子没统一成 0

我第一次写 build 的时候，只处理了根节点存在孩子的情况，根节点缺失的孩子没有补成 0。结果匹配的时候访问trie[u].nxt[R[r] - 'a']，如果这个转移不存在，返回的是 -1，下一步就会拿 -1 去访问 trie，直接 RE。排查了很久，后来打 log 才发现 fl 指针在根节点的一层就出了问题。

修复方式就是 build 里最开始那段：根节点所有不存在的转移统一置为 0。这不仅是边界保护，也是“路径压缩”的一部分。根节点回跳到自己，代码上虽然看起来有点自环的意思，但因为 0 号节点就是空状态，语义上其实是“回到空状态重新开始”。

5.2 匹配 id 和 repair 数组错位

这个坑纯粹是我自己写出来的。一开始我读入规则时遇到空模式串就continue，但 repairList 依然 push 了修复串，导致 id 和 repairList 的下标对不上。后来我把continue放到了 repairList push 之后，保证所有规则都有完整下标，空模式串只是不参与插入匹配。

另外，修复串不一定和模式串等长。比如规则 "abc" -> "longer"，匹配长度是 3，但输出的是 "longer"。我在重构答案时一开始居然用了repairList[matchId[pos]].size()作为覆盖长度，结果区间长度全错了。记住：覆盖长度永远等于 matchLen[pos]，也就是被匹配的原始模式串长度，而不是修复串长度。

5.3 反转之后坐标换算错

这是最容易想错的一步。我最初以为 R 中的右端点 r 对应的原起点 pos 是 N-1-r，这个公式确实没问题，但我在取匹配长度后没有意识到，反转模式串的长度就是原模式串长度，所以覆盖区间直接是 [pos, pos + len)。中间有一版我把区间写成了 [r - len + 1, r] 的镜像，结果全乱套。

后来我强制自己用一段小样例手推了三遍，把所有量都列出来才理清楚：

• 原区间：[pos, pos + len)
• 反转后区间：[N - pos - len, N - 1 - pos]
• 反转后右端点：e = N - 1 - pos
• 由 e 反推原起点：pos = N - 1 - e

这三个式子写下来，代码里才不会凭感觉写。

5.4 输出性能：cout 单字符 TLE

重构答案时我一开始图省事，用cout << S[pos]一个字符一个字符地输出，最后一测果然 TLE。小数据没问题，N 到 10^6 加输出量一大，流式输出就扛不住了。

解决方法是先把所有内容拼到一个 string 里，一次性输出。注意预留空间可以用ans.reserve(n + totalPatternLen)，避免 string 反复扩容造成的拷贝开销。比赛里字符串输出题经常用这个技巧，算是个常规优化。

6. 自测用例与暴力对拍

6.1 三个值得手推的样例

补题完成后我构造了三个测试用例，前两个用于检验匹配规则，第三个专门测坐标换算。

第一个就是前面说过的重叠区间例子。反转移位后，这个样例能覆盖“同一起点长匹配优先”和“重叠后被拒绝”的两种典型情况。

第二个用例用来确认“同一起点选最长”的正确性。起点 0 同时能匹配 "aaa" 和 "aa"，必须选 "aaa"，否则输出就不对。

第三个用例要仔细推一遍。S = "aababc"，起点 0 匹配 "aab"，覆盖 [0, 3)，输出 1。起点 3 的字符是 b，匹配 "bc"，覆盖 [3, 5)，输出 3。最后剩余的 S[5] = 'c' 原样输出。结果 "13c"。这个用例里位置 1 的 "ab" 被起点 0 的匹配覆盖，不能参与替换，正好可以观察覆盖逻辑。

6.2 与 O(NK) 暴力对拍的完整思路

代码 AC 不代表思路一定对，尤其这种规则一大堆的题，最好再写一个暴力对拍。暴力逻辑很简单：枚举每个起点 pos，对每一条规则，检查 S.substr(pos, p.size()) 是否等于 p，记录该起点能匹配到的最长模式串。然后从左到右线性扫描，应用同样的覆盖规则。

暴力的复杂度是 O(N * K * L)，L 是模式串平均长度，只能跑小数据。我写了一个随机数据生成器，N 在 1 到 20，K 在 1 到 6，字符集只有 a、b、c，跑了大概两万组，两边的输出完全一致。这个对拍花的时间不长，但让我对反转坐标和覆盖逻辑都有了信心。强烈建议补字符串题的时候都这么干一遍，很多“我觉得没问题”的隐藏 bug 都是这样被揪出来的。

最后说一点个人体会。这道题真正难的不是 AC 自动机本身，而是把“从左到右贪心选最左最长匹配”这个决策语义，转换成“每个起点只保留一个最长候选”的数据表示。反转文本这个操作，本质上就是 AC 自动机输出数据和题目决策需求之间的桥梁。以后再遇到“替换”“匹配”类题目，我都会先问自己三个问题：替换结果会不会继续参与匹配？重叠区间按什么顺序决策？同一位置的多条匹配选哪条？这三个问题只要有一个没想清楚，代码写得再漂亮都是白给。