这份 U652449 应急故障修复系统replace补题报告我拖了两周才写完。比赛时看到“应急故障修复系统”这个名字我以为是模拟题等看到题面里的 replace 又觉得是字符串替换签到题结果 TLE 了整整四发。下来之后对着样例和残存的比赛记录把题面一点点还原出来才发现这题的核心根本不在“替换”本身而在于“匹配之后怎么决定到底替换哪一段”。如果你也在补这道题或者在做 AC 自动机相关的字符串问题这篇报告应该能帮你少走两三个小时的弯路。1. 题意还原这道题里的 replace 到底有多少隐藏规则1.1 凭赛后记录还原的题面U652449 这套题给的背景名字叫“应急故障修复系统”用户输入的项目标题里也明确写了 replace按我赛后恢复出的题面大致是这样的系统维护一条长度为 N 的文本 S同时有 K 条修复规则每条规则形如 (Pi, Ri)意思是一旦检测到故障片段 Pi就把它修复成 Ri。系统执行规则时会从左到右扫描整条文本。如果在某个位置 pos 能匹配到至少一条规则的 Pi那就必须以这个位置为起点进行一次修复。修复完成后被修复片段覆盖的字符不再参与其他修复系统不会对刚替换进去的内容做二次匹配。输出最终修复完的整条文本。这句话看起来很简单但真正的坑藏在细节里。根据我手头还原出的样例行为题目还隐含了三条规则同一个字符最多只能属于一次修复也就是替换区间不能重叠。如果同一个起点能匹配多个 Pi必须选最长的那条模式串。这样“修复最彻底”不存在只修一半的情况。修复完的结果不会继续参与匹配也就是说不会出现 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 - Xba - 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, poslen)那么在反转文本里rev(Pi) 必然也出现一次并且它的右端点是 e N-1-pos。反过来如果反转文本里某个 rev(Pi) 的匹配右端点是 e那它对应原文本的起点就是 pos N-1-e。这组坐标关系是整个解法的地基。比如 S ababaN 5R ababa。原起点 pos0 的 aba 在 R 里是 aba右端点 4N-1-40对得上。原起点 pos3 的 ba 反转成 ab在 R 里出现在 R[0..1]右端点 1N-1-13也对得上。关键点来了所有从同一个原起点 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; } }; vectorNode trie; int matchLen[MAXS], matchId[MAXS]; vectorstring 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() { queueint 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(); vectorstring 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 三个值得手推的样例补题完成后我构造了三个测试用例前两个用于检验匹配规则第三个专门测坐标换算。输入文本规则期望输出abababaaba - X, bab - YXYaaaaaaaa - X, aa - YXaaababcaab - 1, ab - 2, bc - 313c第一个就是前面说过的重叠区间例子。反转移位后这个样例能覆盖“同一起点长匹配优先”和“重叠后被拒绝”的两种典型情况。第二个用例用来确认“同一起点选最长”的正确性。起点 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 到 20K 在 1 到 6字符集只有 a、b、c跑了大概两万组两边的输出完全一致。这个对拍花的时间不长但让我对反转坐标和覆盖逻辑都有了信心。强烈建议补字符串题的时候都这么干一遍很多“我觉得没问题”的隐藏 bug 都是这样被揪出来的。最后说一点个人体会。这道题真正难的不是 AC 自动机本身而是把“从左到右贪心选最左最长匹配”这个决策语义转换成“每个起点只保留一个最长候选”的数据表示。反转文本这个操作本质上就是 AC 自动机输出数据和题目决策需求之间的桥梁。以后再遇到“替换”“匹配”类题目我都会先问自己三个问题替换结果会不会继续参与匹配重叠区间按什么顺序决策同一位置的多条匹配选哪条这三个问题只要有一个没想清楚代码写得再漂亮都是白给。
