1. 从一道题看字符串匹配与计数的交叉地带如果你刷过一段时间的算法题看到Censored!这个标题大概会心一笑——这是一道把AC自动机、动态规划和大数运算揉在一起的经典题。它的核心场景很直白给定若干个禁忌单词问长度为L的字符串中有多少个不包含任何禁忌单词的字符串。字母表大小、禁忌词数量、目标长度都是变量答案可能大到超出64位整数范围所以还得手写高精度。我第一次遇到这道题的时候第一反应是这不就是个简单的DP吗结果写完发现两个致命问题一是状态转移时怎么判断当前拼接的字符会不会构成禁忌词二是答案的位数可能上百位用long long直接溢出。后来才意识到这题真正的门槛不在DP本身而在于如何把AC自动机的状态机嵌入到DP的转移方程里以及如何优雅地处理大数加法。这篇文章我会从零开始拆解这道题的完整解法。不管你是刚学完AC自动机想找个综合题练手还是被高精度和DP的组合卡住了思路我都会把每一步的推导过程、代码实现的细节、以及我踩过的坑讲清楚。核心关键词就三个AC自动机建图、DP状态转移、高精度加法。读完你不仅能AC这道题更重要的是能理解自动机DP这类题目的通用套路。2. 为什么这题不能只用KMP或者暴力匹配2.1 暴力思路的复杂度分析先说说最朴素的想法。假设字母表有m个字符目标长度是L那总共有m^L个字符串。对每个字符串用KMP去检查是否包含任何一个禁忌词。禁忌词有n个每个长度不超过p。那么总复杂度大约是O(m^L × n × (Lp))。当L100、m50的时候m^L是一个天文数字完全不可行。即使我们换一种思路用DP逐位构造字符串每构造一位就检查所有禁忌词是否出现在后缀中复杂度也不低。假设当前构造到第i位我们需要检查以第i位结尾的所有后缀是否匹配某个禁忌词。如果每个状态都暴力检查单次转移就是O(n×p)总复杂度O(L×m×n×p)。在L100、m50、n50、p10的规模下大约是250万次操作看起来还行但问题是这种暴力检查无法复用之前匹配的信息每次都要从头比对。2.2 AC自动机带来的状态压缩AC自动机的价值就在这里。它把所有禁忌词构建成一棵Trie树然后通过fail指针把树上的节点连成一个状态转移图。在这个图上每个节点代表当前已经匹配到的最长前缀而fail指针指向的是当前后缀能匹配到的最长前缀。这样一来当我们从某个状态出发读入一个字符时只需要沿着转移边走到下一个状态就能知道当前是否匹配到了某个禁忌词。关键点在于AC自动机的状态数是有限的最多是所有禁忌词的总长度加一根节点。假设总长度为S那么状态数就是S1。在DP过程中我们只需要记录当前在AC自动机的哪个节点而不需要记录完整的字符串历史。这就是状态压缩的核心——用自动机的节点编号代替字符串后缀信息。具体来说如果我们在构建AC自动机时把每个节点的转移边都补全即对于不存在的子节点让它指向fail指针的对应子节点那么从任意状态读入任意字符都能在O(1)时间内找到下一个状态。这样DP的转移就是O(L×S×m)其中S是自动机节点数m是字母表大小。在典型数据下S不超过100m不超过50L不超过100总操作数约50万次完全可行。2.3 禁忌标记的传递还有一个容易被忽略的细节如果一个节点本身不是禁忌词的结尾但它的fail指针指向的节点是禁忌词结尾那么这个节点也应该被标记为危险状态。原因很简单当你在当前节点时你的后缀已经包含了那个禁忌词。所以在构建AC自动机时我们需要在BFS求fail指针的过程中把危险标记沿着fail边传递下去。这一步如果漏掉会导致DP过程中把一些实际上包含禁忌词的字符串误判为合法。我当初就犯过这个错误样例过了但提交WA排查了半天才发现是标记没传递。3. AC自动机的构建细节与转移图补全3.1 Trie树的插入与节点结构设计先定义节点结构。每个节点需要包含子节点指针数组大小为字母表大小、fail指针、以及一个布尔标记表示该节点是否为禁忌词结尾或其后缀包含禁忌词。struct Node { int next[52]; // 假设字母表是大小写字母共52个 int fail; bool danger; Node() { memset(next, -1, sizeof(next)); fail 0; danger false; } };这里用-1表示子节点不存在方便后续补全转移图。字母表映射需要根据题目给定的字符集来定比如题目可能只给大写字母那就映射到0-25。插入过程就是标准的Trie插入从根节点出发对每个字符找到对应子节点不存在就新建最后在末尾节点标记dangertrue。3.2 BFS构建fail指针与危险标记传递构建fail指针用BFS层次遍历。根节点的所有直接子节点的fail指向根节点。对于其他节点假设当前节点u通过字符c指向子节点v那么v的fail指针应该是u的fail指针通过字符c到达的节点。void build() { queueint q; for (int c 0; c 52; c) { if (nodes[0].next[c] ! -1) { nodes[nodes[0].next[c]].fail 0; q.push(nodes[0].next[c]); } else { nodes[0].next[c] 0; // 补全转移图 } } while (!q.empty()) { int u q.front(); q.pop(); if (nodes[nodes[u].fail].danger) nodes[u].danger true; // 危险标记传递 for (int c 0; c 52; c) { if (nodes[u].next[c] ! -1) { int v nodes[u].next[c]; nodes[v].fail nodes[nodes[u].fail].next[c]; q.push(v); } else { nodes[u].next[c] nodes[nodes[u].fail].next[c]; } } } }注意这里在BFS过程中同时做了两件事一是传递危险标记二是补全转移图。补全转移图的意思是对于不存在的子节点直接让它指向fail指针的对应子节点。这样在DP转移时我们不需要再沿着fail链跳转直接查表就能得到下一个状态。提示危险标记的传递必须在BFS的每一层都做不能只在插入时标记。因为一个节点的fail指针可能指向另一个危险节点这种情况下当前节点也应该是危险的。3.3 转移图的验证方法构建完自动机后建议手动验证几个关键转移。比如对于禁忌词集合{AB, BC}从根节点读入A应该到节点A再读入B应该到节点AB危险再读入C应该到节点BC危险。如果从节点A读入C应该转移到节点C因为fail链上A的fail是根根的C子节点是C。验证的方法很简单写一个小函数打印每个状态读入每个字符后的转移目标然后人工检查几个边界情况。这一步虽然看起来笨但能帮你提前发现构建逻辑的错误比提交后WA再回来调试高效得多。4. DP状态定义与转移方程的推导过程4.1 状态定义为什么是dp[i][j]而不是dp[i][j][k]最直观的DP定义是dp[i][j]表示长度为i、当前在AC自动机节点j上的合法字符串数量。这里合法指的是整个字符串中不包含任何禁忌词。为什么不需要额外的维度因为AC自动机的节点已经隐含了所有必要的后缀信息。节点j代表了当前字符串的最长可匹配后缀而危险标记已经帮我们排除了包含禁忌词的情况。所以只要当前节点不是危险节点就说明到目前为止构造的字符串是合法的。转移方程也很直接dp[i1][next[j][c]] dp[i][j]其中next[j][c]是从节点j读入字符c后到达的节点且next[j][c]不能是危险节点。4.2 初始状态与边界条件初始状态是dp[0][0] 1表示长度为0的字符串在根节点数量为1。其他dp[0][j] 0。边界条件是如果某个节点是危险的那么所有到达该节点的转移都应该被跳过。另外如果根节点本身是危险的即存在空字符串禁忌词那答案直接是0。不过通常题目不会给空串但代码里加个判断更稳妥。最终答案是sum(dp[L][j])对所有非危险节点j求和。4.3 转移顺序与滚动数组优化由于dp[i1]只依赖于dp[i]我们可以用滚动数组把空间从O(L×S)降到O(S)。但要注意高精度加法不能用简单的赋值需要每次清空下一层数组。// 伪代码示意 dp[0][0] 1; for (int i 0; i L; i) { clear(dp[(i1)%2]); // 清空下一层 for (int j 0; j nodeCount; j) { if (nodes[j].danger) continue; for (int c 0; c alphabetSize; c) { int nj nodes[j].next[c]; if (nodes[nj].danger) continue; dp[(i1)%2][nj] dp[i%2][j]; } } }这里的高精度加法需要自己实现因为C的long long最多只能表示约9.2×10^18而答案可能有上百位。5. 高精度加法的实现与性能考量5.1 为什么不能用__int128或者大数库有些同学可能会想用__int128是不是就够了__int128最大约1.7×10^38对于L100、字母表52的情况答案大约是52^100≈10^171远远超出__int128的范围。所以必须手写高精度。至于现成的大数库比如GMP在算法竞赛中通常不允许使用而且引入外部库也会增加编译和调试的复杂度。手写一个简单的高精度加法反而更可控。5.2 高精度加法的实现细节高精度数的表示方式有很多种最常见的是用数组存储每一位数字低位在前。加法就是从低位到高位逐位相加处理进位。struct BigInt { vectorint digits; // 低位在前 BigInt() { digits.push_back(0); } BigInt(int x) { while (x) { digits.push_back(x % 10); x / 10; } if (digits.empty()) digits.push_back(0); } void add(const BigInt other) { int carry 0; int n max(digits.size(), other.digits.size()); digits.resize(n, 0); for (int i 0; i n; i) { int sum digits[i] (i other.digits.size() ? other.digits[i] : 0) carry; digits[i] sum % 10; carry sum / 10; } if (carry) digits.push_back(carry); } };这个实现的时间复杂度是O(位数)每次加法最多处理当前数字的位数。在DP过程中每个状态的高精度数位数会逐渐增长但总体复杂度仍然可以接受。5.3 性能优化避免频繁的内存分配如果每个dp状态都用一个vector在转移过程中会频繁进行内存分配和释放影响性能。一个优化思路是用固定大小的数组比如每个高精度数最多200位用int数组存储。这样避免了动态内存管理速度会快很多。int dp[2][MAXN][MAXD]; // MAXN是节点数MAXD是最大位数 int len[2][MAXN]; // 记录每个数的实际位数加法操作直接在这个数组上进行效率会明显提升。当然具体用哪种方式取决于题目规模和你的编码习惯。如果L比较小用vector也完全够用。注意高精度加法的进位处理要小心特别是当两个数位数不同时不要漏掉较长那个数的高位。我见过有人在循环里只处理到较短数的长度结果高位丢失导致答案错误。6. 完整代码框架与关键模块拆解6.1 整体流程梳理整个程序的流程可以分成四步读入数据并映射字符集、构建AC自动机、DP转移、输出答案。每一步都有一些容易出错的细节下面逐一说明。读入数据时需要注意字母表的映射。题目可能给的是大写字母、小写字母或者大小写混合。我们需要建立一个映射表把每个字符映射到0到m-1的整数。同时禁忌词和目标字符串都使用这个映射。构建AC自动机时节点数最多是所有禁忌词长度之和加一。数组大小要开够否则会越界。DP转移时注意滚动数组的清空和状态的有效性检查。输出答案时从高位到低位打印注意去掉前导零但至少保留一位。6.2 字符集映射的坑字符集映射看起来简单但有一个容易忽略的点题目给的字母表可能不是连续的。比如题目说字母表是{A, C, G, T}那映射就是A→0, C→1, G→2, T→3。但如果题目说字母表是26个小写字母那映射就是a→0, b→1, ..., z→25。还有一种情况是题目给的字母表包含特殊字符比如数字和字母混合。这时候需要仔细读题确保映射正确。我建议在代码里用一个map或者数组来存储映射关系而不是硬编码。6.3 节点数上限的估算节点数上限等于所有禁忌词的总长度加一。假设有n个禁忌词每个长度不超过p那么节点数最多是n×p1。在开数组时这个值要留一些余量比如多开10个节点防止边界情况越界。如果题目没有明确给出n和p的范围可以根据题目描述中的约束来估算。比如POJ 1625这道题禁忌词数量不超过50每个长度不超过10那么节点数最多501。开600的数组就足够了。6.4 代码实现中的常见错误第一个常见错误是忘记传递危险标记。前面已经强调过这里再提一次在BFS求fail指针时如果fail指向的节点是危险的当前节点也要标记为危险。第二个常见错误是高精度加法的进位丢失。特别是在滚动数组优化时下一层数组没有清空导致上一轮的数据残留。第三个常见错误是DP转移时没有跳过危险节点。有些同学只在最终求和时检查危险标记但转移过程中如果进入了危险节点后续的转移都是无效的应该提前跳过。第四个常见错误是字母表大小和实际字符数不一致。比如题目说字母表是26个大写字母但代码里只开了26个转移边结果映射时用了小写字母的ASCII值导致越界。7. 实测中的边界情况与调试技巧7.1 空串和单字符的边界测试测试时先从最简单的case开始。比如L0答案应该是1空串。L1如果字母表是{a,b}禁忌词是{a}那答案应该是1只有b合法。这些边界case能帮你验证DP的初始状态和转移逻辑是否正确。如果L0时输出0那说明初始状态设置有问题如果L1时答案不对那可能是转移或危险标记的问题。7.2 大数输出的验证方法高精度加法的验证比较麻烦因为答案可能很大。一个实用的技巧是先用小规模数据测试确保答案在long long范围内时高精度结果和long long结果一致。然后再用大规模数据测试检查输出格式是否正确没有前导零、位数正确。另外可以用Python写一个暴力程序来对拍。Python自带大整数不需要手写高精度非常适合用来验证C程序的正确性。7.3 对拍脚本的编写思路对拍的基本思路是随机生成小规模测试数据分别用暴力程序和你写的程序运行比较输出是否一致。暴力程序可以用Python写直接枚举所有字符串并检查是否包含禁忌词。# Python暴力示意 import itertools def brute(alphabet, forbidden, L): count 0 for s in itertools.product(alphabet, repeatL): t .join(s) if not any(f in t for f in forbidden): count 1 return count对拍时注意控制数据规模L不要超过6字母表不要超过3否则暴力程序会跑得太慢。7.4 性能瓶颈的定位如果程序超时首先检查AC自动机的构建是否有冗余操作。比如在BFS中如果每次都遍历所有52个字符而实际字母表只有4个字符那就有大量无用操作。可以把字母表大小作为参数传入只遍历实际用到的字符。其次检查DP转移的循环顺序。把节点循环放在外层、字符循环放在内层可以利用CPU缓存提高访问效率。如果反过来每次跳转到不同的节点缓存命中率会降低。最后检查高精度加法的实现。如果每次加法都重新分配内存可以考虑用固定数组或者预分配空间。另外如果答案的位数远小于最大位数可以在加法时只处理到实际位数避免无用的零运算。8. 从这道题延伸出的通用解题框架8.1 AC自动机DP的适用场景这类题目的共同特征是在一个字符集上构造字符串要求满足某些与子串匹配相关的约束求满足条件的字符串数量或最优值。AC自动机负责把子串匹配的约束转化为状态转移图上的节点标记DP负责在图上进行计数或优化。类似的题目还有给定若干禁止模式求长度为L的字符串中不包含任何禁止模式的方案数或者给定若干模式每个模式有一个权值求长度为L的字符串的最大权值和。这些题目的核心思路都是一样的只是DP的目标函数不同。8.2 状态设计的通用思路状态设计的关键是找到最小的信息集合使得未来的转移只依赖于这个集合。在AC自动机DP的题目中这个集合就是当前在自动机上的节点。因为自动机节点已经编码了所有与模式匹配相关的后缀信息所以不需要额外的维度。如果题目还有其他约束比如字符的使用次数限制那就需要在状态中增加相应的维度。但一般来说AC自动机节点是必须的其他维度根据题目要求添加。8.3 高精度在计数问题中的必要性当计数问题的答案可能超出64位整数范围时就需要高精度。判断是否需要高精度的简单方法是估算答案的上界。比如字母表大小为m长度为L那答案最多是m^L。如果m^L大于2^63-1就需要高精度。在竞赛中高精度加法是最常用的操作偶尔也会用到高精度乘法。手写一个简洁的高精度模板能在很多题目中复用。8.4 调试这类题目的系统方法调试AC自动机DP高精度的题目建议按照以下顺序排查先验证AC自动机构建是否正确打印转移表再验证DP转移是否正确用小规模数据对拍最后验证高精度加法是否正确与Python结果对比。每一步都确认无误后再组合起来测试。这种分模块调试的方法比直接调试整个程序高效得多因为你可以快速定位问题出在哪个模块。我当初就是没有分模块调试导致在一个小错误上浪费了大量时间。9. 我在实现过程中积累的几个实用技巧第一个技巧是关于危险标记的。除了在BFS中传递危险标记还可以在DP转移时做二次检查。具体来说即使某个节点没有被标记为危险但如果它的fail链上存在危险节点那它实际上也是危险的。不过如果BFS中已经正确传递了标记这一步就是多余的。我建议在BFS中做好传递DP中就不用再检查了这样效率更高。第二个技巧是关于高精度加法的。如果答案的位数可能达到几百位用vector的动态扩容会有性能开销。一个简单的优化是预估最大位数然后一次性分配足够的空间。比如L100、m52时最大位数大约是171位那就可以预分配200位的数组。第三个技巧是关于滚动数组的。滚动数组虽然节省空间但容易出错。如果空间足够建议先用二维数组写一版确认逻辑正确后再改成滚动数组。这样调试起来更直观不容易被下标问题困扰。第四个技巧是关于字符映射的。如果题目给的字母表是连续的ASCII字符比如A到Z可以直接用字符减去A来映射。但如果是离散的字符集建议用一个数组或map来存储映射关系避免硬编码出错。第五个技巧是关于对拍的。对拍是验证程序正确性的利器但要注意控制数据规模。如果暴力程序跑得太慢可以只对拍小规模数据然后用中等规模数据检查程序的运行时间是否合理。10. 关于这道题的一些个人体会这道题我前前后后做了三次才完全AC。第一次是AC自动机的危险标记没传递第二次是高精度加法的进位处理有bug第三次是滚动数组的清空逻辑写错了。每次调试都让我对这几个知识点有了更深的理解。现在回头看这道题的价值不在于它本身有多难而在于它把三个重要的知识点串联在了一起。AC自动机是字符串匹配的利器DP是计数问题的通用框架高精度是处理大数的必备技能。能把这三者结合起来解决问题说明你对每个知识点都有了扎实的掌握。如果你正在学AC自动机我建议先把基础的匹配问题做熟再尝试这道题。如果你已经会AC自动机但没做过DP结合那这道题是一个很好的过渡。如果你连高精度都没写过那正好借这道题练练手。最后分享一个小心得写这类综合题时不要想着一次写对。先把框架搭起来用最简单的数据测试每个模块确认无误后再组合。这样即使出错也能快速定位问题。我在实际编码中通常会先写AC自动机的构建和打印函数确认转移图正确后再写DP和高精度。这种分步验证的方法比一口气写完再调试要高效得多。