AC自动机+DP+高精度：统计不含禁用词的字符串数量

1. 从一道题看字符串匹配与计数的完整技术链路字符串匹配类的算法题里有一类特别有意思的题型给定一个字符集要求统计长度为某个值的、不包含任何禁用词的字符串有多少个。这类问题表面上看是计数问题实际上它把多模式串匹配和动态规划这两块知识缝合在了一起再加上结果可能大到爆long long还得叠一层高精度运算。三个技术点串成一条线任何一个环节掉链子都过不了。Censored!这道题就是这类题型的典型代表。它的核心设定是给你一个字符集注意字符集不一定是小写字母可能是任意可见字符再给你若干个禁忌单词问你在长度为L的所有字符串中有多少个字符串不包含任何一个禁忌单词作为子串。答案要对一个大数取模不这道题不取模答案可能极其巨大所以必须用高精度。为什么这道题值得单独拿出来讲因为它把AC自动机Aho-Corasick Automaton的状态转移特性用到了极致。AC自动机本身是用来做多模式匹配的但在这道题里它的每一个节点代表当前已经匹配了哪些前缀的状态而DP的过程就是在AC自动机的状态图上走L步统计不经过任何危险节点的路径条数。这个思路一旦理解透了类似的题目比如统计不含某些子串的字符串数量、DNA序列计数等都能一通百通。这篇文章适合谁看如果你已经学过AC自动机的基本构建但对AC自动机DP的组合还不太熟练或者你对高精度运算在算法题中的应用场景不太清楚那这篇内容会帮你把整条链路打通。如果你是完全的新手建议先补一下Trie树和KMP的基本概念否则后面的状态转移部分会有点吃力。我会尽量用生活化的类比来解释但该有的技术细节一个都不会少。接下来我会从整体设计思路开始拆然后逐个环节讲实现细节再给出一套可以直接参考的代码框架最后把我踩过的坑和常见问题整理出来。整篇内容基于我自己的实操经验不是教科书式的复述。2. 整体方案设计与核心思路拆解2.1 为什么是AC自动机而不是KMP或后缀自动机先想清楚一个问题我们要统计的是不包含任何禁忌单词的字符串数量。禁忌单词有多个而且长度不一。如果只用KMP每次只能匹配一个模式串多个模式串就得跑多遍而且DP的状态没法统一表示当前匹配到了哪些模式串的什么位置。AC自动机的优势在于它把所有模式串建成一棵Trie树然后通过fail指针把树变成了图。在这张图上每个节点代表一个匹配状态——你当前扫描到的字符串对应着Trie树上的某个节点这个节点隐含了当前后缀匹配了哪些模式串的前缀这个信息。换句话说AC自动机的节点天然就是DP的状态。那后缀自动机SAM行不行SAM更适合处理单个字符串的所有子串问题对于多模式串的匹配场景AC自动机更直接。而且这道题需要的是路径计数AC自动机的状态转移图正好是一个确定性的自动机每个状态读入一个字符后跳转到唯一的下一个状态非常适合做DP。这里有个关键认知AC自动机不只是一个匹配工具它本质上是一个DFA确定性有限自动机。DFA的每个状态在给定输入字符后都有唯一的转移目标这个性质是DP能够成立的前提。2.2 DP状态的定义与转移方程定义dp[i][j]表示长度为i的字符串当前在AC自动机上处于状态j时不包含任何禁忌单词的方案数。转移方程很直观dp[i1][next_state] dp[i][j]其中next_state trie[j].next[c]c是字符集中的某个字符。但有一个前提next_state不能是危险节点。什么是危险节点两类本身就是某个禁忌单词的结尾节点通过fail指针间接指向了禁忌单词结尾的节点因为fail指针指向的是当前状态的最长后缀如果那个后缀是禁忌单词那当前状态也脏了所以构建完AC自动机后需要做一遍危险标记的下传如果某个节点的fail指向的节点是危险的那这个节点也是危险的。这一步在BFS构建fail指针的时候顺便就能做。最终答案是sum(dp[L][j])其中j遍历所有非危险节点。2.3 高精度为什么必须上题目中字符串长度L可以到很大具体上限看题目数据范围字符集大小也可能不小。即使字符集只有26个字母L50的时候26^50已经是天文数字了远超unsigned long long的范围大约1.8×10^19。所以必须用高精度。高精度在这里的实现方式有两种选择用大数类比如Java的BigInteger或者C手写高精度用数组模拟大整数加法因为DP的转移只涉及加法不涉及乘法所以高精度只需要实现加法就够了。这大大简化了实现难度。每次转移就是两个高精度数相加写一个bigAdd函数即可。实操心得很多人一看到高精度就头疼觉得要写乘法、除法、取模。但这道题只需要加法你甚至可以用vectorint存每一位写一个20行的加法函数就搞定了。不要被高精度三个字吓到。3. 核心细节解析与实操要点3.1 字符集的处理不是所有题都是小写字母这道题的第一个坑就是字符集。很多AC自动机的模板题默认字符集是小写字母a-z数组开26就够了。但Censored!的字符集是给定的可能包含大写字母、数字、甚至符号而且字符的ASCII码不一定连续。处理方式先把所有出现的字符收集起来做一个字符到编号的映射。比如字符集是{A, C, G, T}那就建立映射A-0, C-1, G-2, T-3。Trie树的next数组大小就是字符集大小而不是256或26。mapchar, int charId; string charset; // 输入的字符集 for (int i 0; i charset.size(); i) { charId[charset[i]] i; }这样做的好处是节省空间而且转移的时候直接用编号不需要每次都查ASCII表。坏处是如果字符集很大比如全部256个字符那每个节点的next数组就会很大内存消耗高。这时候可以用map或者哈希来代替数组但会慢一些。对于这道题的数据规模数组通常够用。3.2 Trie树的构建细节Trie树的每个节点需要存next[]转移数组fail失配指针danger是否是危险节点构建过程就是标准的Trie插入。每插入一个禁忌单词在最后一个字符对应的节点上标记danger true。struct Node { int next[MaxChar]; int fail; bool danger; Node() { memset(next, 0, sizeof(next)); fail 0; danger false; } };注意根节点是0号节点初始化的时候所有next指向0也就是根这表示没有这个转移。注意事项如果你的字符集编号从0开始那next[c]0会有歧义——它既表示转移到根节点又表示没有这个转移。解决办法是让根节点编号为0但真正的转移目标从1开始编号或者用一个单独的exist数组标记转移是否存在。我个人的习惯是把根节点设为0所有不存在的转移也指向0然后在BFS构建fail的时候特殊处理根节点的子节点。3.3 Fail指针的构建与危险标记下传Fail指针的构建用BFS。核心逻辑根节点的所有存在的子节点的fail指向根节点入队。对于队列中的每个节点u遍历它的所有转移c如果u.next[c]存在那u.next[c].fail u.fail.next[c]如果不存在直接让u.next[c] u.fail.next[c]路径压缩这是AC自动机变成DFA的关键一步如果u.next[c]是危险节点它自己danger或者它fail指向的节点danger标记为危险void build() { queueint q; for (int c 0; c charSize; c) { if (trie[0].next[c]) { trie[trie[0].next[c]].fail 0; q.push(trie[0].next[c]); } } while (!q.empty()) { int u q.front(); q.pop(); // 危险标记下传 if (trie[trie[u].fail].danger) { trie[u].danger true; } for (int c 0; c charSize; c) { int v trie[u].next[c]; if (v) { trie[v].fail trie[trie[u].fail].next[c]; q.push(v); } else { trie[u].next[c] trie[trie[u].fail].next[c]; } } } }这里有个细节危险标记的下传必须在BFS的过程中做因为fail指针是指向层数更小的节点BFS保证了处理当前节点时它的fail指向的节点已经被处理过了。实操心得路径压缩trie[u].next[c] trie[trie[u].fail].next[c]这一步非常关键。它让AC自动机从一棵树变成了一张图每个状态对每个字符都有确定的转移。这样DP的时候就不需要沿着fail链跳来跳去了直接O(1)转移。很多人写AC自动机的时候不做路径压缩DP的时候每次都要跳fail复杂度直接爆炸。3.4 DP的初始化与边界条件DP数组dp[i][j]i从0到Lj从0到节点总数。初始化dp[0][0] 1其余为0。意思是长度为0的字符串在根节点方案数为1。转移对于每个i从0到L-1对于每个非危险节点j如果dp[i][j] 0则对于字符集中的每个字符c计算nj trie[j].next[c]如果nj不是危险节点则dp[i1][nj] dp[i][j]。最终答案sum(dp[L][j])j遍历所有非危险节点。注意事项如果根节点本身是危险节点比如某个禁忌单词是空串那答案直接是0。但通常题目不会给空串所以可以忽略。不过严谨起见还是判断一下。3.5 高精度加法的实现因为只需要加法实现非常简单。用一个vectorint存每一位低位在前。加法就是从低位到高位逐位相加处理进位。vectorint bigAdd(vectorint a, vectorint b) { vectorint res; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; res.push_back(sum % 10); carry sum / 10; } return res; }在DP中每次转移就是一次bigAdd。为了效率可以用一个三维数组dp[i][j]每个元素是一个vectorint。但这样内存消耗大而且vector的拷贝开销高。优化方式是滚动数组只保留当前层和下一层。实操心得高精度加法虽然简单但在DP中频繁调用会有性能问题。我的做法是预估答案的最大位数然后用固定大小的数组比如int dp[2][MaxNode][MaxDigits]来存避免vector的动态分配。最大位数可以估算字符集大小^L取对数就能算出位数上限。比如26^50大约是10^70那就开100位足够了。4. 完整实操流程与核心环节实现4.1 输入解析与字符集映射先读入字符集和禁忌单词数量然后读入每个禁忌单词。注意字符集可能包含空格所以读入的时候要用getline或者逐个字符读。int N, L; string charset; cin N L; cin charset; int charSize charset.size(); mapchar, int charId; for (int i 0; i charSize; i) { charId[charset[i]] i; }然后读入N个禁忌单词插入Trie树。for (int i 0; i N; i) { string word; cin word; insert(word); }插入函数void insert(string s) { int u 0; for (char ch : s) { int c charId[ch]; if (!trie[u].next[c]) { trie[u].next[c] tot; } u trie[u].next[c]; } trie[u].danger true; }4.2 AC自动机构建与危险节点标记按照前面讲的BFS方式构建fail指针同时做路径压缩和危险标记下传。这一步是整个算法的核心写错了后面全错。void build() { queueint q; for (int c 0; c charSize; c) { int v trie[0].next[c]; if (v) { trie[v].fail 0; q.push(v); } } while (!q.empty()) { int u q.front(); q.pop(); if (trie[trie[u].fail].danger) { trie[u].danger true; } for (int c 0; c charSize; c) { int v trie[u].next[c]; if (v) { trie[v].fail trie[trie[u].fail].next[c]; q.push(v); } else { trie[u].next[c] trie[trie[u].fail].next[c]; } } } }注意危险标记下传必须在处理当前节点的子节点之前做因为子节点的fail可能指向当前节点。如果当前节点是危险的子节点也会被标记为危险。这个顺序不能乱。4.3 DP转移与高精度加法用滚动数组优化空间。dp[0]表示当前层dp[1]表示下一层。每轮结束后交换。// 初始化 dp[0][0] {1}; // 高精度数1 int cur 0; for (int i 0; i L; i) { // 清空下一层 for (int j 0; j tot; j) { dp[1-cur][j].clear(); } for (int j 0; j tot; j) { if (trie[j].danger) continue; if (dp[cur][j].empty()) continue; for (int c 0; c charSize; c) { int nj trie[j].next[c]; if (trie[nj].danger) continue; dp[1-cur][nj] bigAdd(dp[1-cur][nj], dp[cur][j]); } } cur 1 - cur; }最后统计答案vectorint ans {0}; for (int j 0; j tot; j) { if (!trie[j].danger) { ans bigAdd(ans, dp[cur][j]); } } // 输出ans从高位到低位4.4 高精度输出的细节高精度数存的时候是低位在前输出的时候要反过来。而且要注意去掉前导零但至少保留一位。void printBig(vectorint a) { if (a.empty()) { cout 0; return; } for (int i a.size() - 1; i 0; i--) { cout a[i]; } }实操心得高精度加法中如果两个数都是0结果应该是0但我的bigAdd实现会返回一个空的vector或者只含一个0的vector。输出的时候要处理这种情况。另外如果答案是0比如所有路径都被禁忌单词堵死了也要正确输出0。4.5 完整代码框架把上面的片段拼起来就是一个完整的解法。我把它整理成一个可以直接参考的框架#include bits/stdc.h using namespace std; const int MAXN 105; // 最大节点数 const int MAXD 200; // 最大位数 struct Node { int next[60]; int fail; bool danger; Node() { memset(next, 0, sizeof(next)); fail 0; danger false; } } trie[MAXN]; int tot 0; mapchar, int charId; int charSize; void insert(string s) { int u 0; for (char ch : s) { int c charId[ch]; if (!trie[u].next[c]) { trie[u].next[c] tot; } u trie[u].next[c]; } trie[u].danger true; } void build() { queueint q; for (int c 0; c charSize; c) { int v trie[0].next[c]; if (v) { trie[v].fail 0; q.push(v); } } while (!q.empty()) { int u q.front(); q.pop(); if (trie[trie[u].fail].danger) { trie[u].danger true; } for (int c 0; c charSize; c) { int v trie[u].next[c]; if (v) { trie[v].fail trie[trie[u].fail].next[c]; q.push(v); } else { trie[u].next[c] trie[trie[u].fail].next[c]; } } } } vectorint bigAdd(const vectorint a, const vectorint b) { vectorint res; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n || carry; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; res.push_back(sum % 10); carry sum / 10; } return res; } int main() { int N, L; string charset; cin N L; cin charset; charSize charset.size(); for (int i 0; i charSize; i) { charId[charset[i]] i; } for (int i 0; i N; i) { string word; cin word; insert(word); } build(); vectorvectorint dp[2]; dp[0].resize(tot 1); dp[1].resize(tot 1); dp[0][0] {1}; int cur 0; for (int i 0; i L; i) { for (int j 0; j tot; j) { dp[1-cur][j].clear(); } for (int j 0; j tot; j) { if (trie[j].danger || dp[cur][j].empty()) continue; for (int c 0; c charSize; c) { int nj trie[j].next[c]; if (trie[nj].danger) continue; dp[1-cur][nj] bigAdd(dp[1-cur][nj], dp[cur][j]); } } cur 1 - cur; } vectorint ans {0}; for (int j 0; j tot; j) { if (!trie[j].danger) { ans bigAdd(ans, dp[cur][j]); } } for (int i ans.size() - 1; i 0; i--) { cout ans[i]; } cout endl; return 0; }这个框架可以直接用只需要根据题目的数据范围调整MAXN和MAXD。5. 常见问题与排查技巧实录5.1 答案总是偏小或者为0这是最常见的问题。原因通常是危险节点标记不完整。检查以下几点插入禁忌单词时最后一个节点的danger是否设为trueBFS构建fail时是否做了危险标记下传也就是if (trie[trie[u].fail].danger) trie[u].danger true;路径压缩后trie[u].next[c]可能指向一个危险节点DP转移时是否检查了trie[nj].danger我遇到过一种情况禁忌单词A是禁忌单词B的前缀比如AabBabc。插入ab时标记了节点2为危险插入abc时节点3也是危险。但如果没有做危险标记下传节点3的fail指向节点2因为abc的最长后缀bc不在Trie中再跳fail到c也不在最后到根实际上abc的fail应该指向bc对应的节点如果bc不存在则指向根。这种情况下节点3自己就是危险的所以没问题。但如果BxabcAabc那B的某个前缀节点可能通过fail指向A的结尾节点这时候就必须靠危险标记下传来标记了。5.2 高精度加法结果不对高精度加法的常见错误进位处理遗漏循环条件要包含carry否则最高位的进位会丢失。前导零问题输出时从高位到低位但最高位可能是0比如结果就是0需要特殊处理。数组越界如果预估的位数不够加法结果会截断。建议开大一点比如200位。避坑技巧可以在本地用Python的BigInteger验证小数据的结果对比C高精度的输出。比如L10字符集大小2禁忌单词1个手动算一下或者用Python跑一下看看结果是否一致。5.3 内存超限或运行超时如果节点数很多比如禁忌单词总长度很大dp数组会很大。优化方式用滚动数组只保留两层。高精度数用固定大小数组而不是vector减少动态分配。如果字符集很大next数组用map或者哈希但会慢一些。权衡一下通常数组更快。另一个超时原因是DP转移时对每个状态都遍历所有字符。如果字符集大小是60节点数是100L是50那总转移次数是50×100×60300000次每次还要做高精度加法。高精度加法如果位数是200那每次加法是200次操作总共6000万次操作勉强能过。如果超时可以优化高精度加法比如用int数组存多位压位一次处理9位。5.4 常见问题速查表问题现象可能原因排查方法解决方案答案为0危险节点标记过多检查根节点是否被标记为危险确保空串不被视为禁忌单词答案偏小危险标记下传遗漏打印每个节点的danger状态在BFS中补充下传逻辑答案偏大危险节点未被排除检查DP转移时的danger判断转移前检查trie[nj].danger高精度结果截断位数预估不足计算字符集大小^L的位数开更大的MAXD运行超时高精度加法太慢统计加法调用次数压位优化或减少状态数编译错误数组大小不够检查MAXN和字符集大小根据题目范围调整5.5 独家避坑技巧第一个技巧在本地用小数据暴力验证。写一个暴力枚举所有长度为L的字符串检查是否包含禁忌单词统计数量。然后和AC自动机DP的结果对比。这个方法能快速定位是AC自动机的问题还是DP的问题。第二个技巧打印AC自动机的状态转移图。对于小规模的字符集和禁忌单词把每个节点的next、fail、danger都打印出来肉眼检查一遍。很多时候错误就藏在某个节点的fail指针上。第三个技巧高精度加法用Python验证。把DP的转移过程用Python重写一遍用Python的int直接算对比C高精度的输出。如果Python的结果和C不一致那就是高精度实现有问题如果一致但和暴力不一致那就是DP或AC自动机的问题。第四个技巧注意字符集的读入。有些题目的字符集可能包含空格或者特殊字符用cin charset可能会读不全。建议用getline或者逐个字符读入。我在这道题上踩过坑字符集里有个空格结果读入的时候被截断了导致后面映射出错。6. 从这道题延伸出去的知识链路6.1 AC自动机DP的通用套路这道题的核心套路可以总结为在DFA上做路径计数。AC自动机构建出来的就是一张DFA每个状态代表匹配进度每条边代表读入一个字符。DP的过程就是在DFA上走L步统计不经过禁止状态的路径数。这个套路可以推广到很多问题统计不含某些子串的字符串数量就是这道题统计DNA序列中不含某些模式的数量统计密码中不含某些敏感词的数量甚至可以用矩阵快速幂优化当L特别大的时候如果L达到10^9级别DP的O(L×状态数×字符集)就扛不住了。这时候可以把DFA的转移矩阵建出来用矩阵快速幂加速。但矩阵中的元素是高精度数矩阵乘法会非常慢。通常这种题会要求取模那就简单了。6.2 高精度在算法题中的常见场景高精度运算在算法题中出现通常是因为答案超出了基本数据类型的范围。常见场景组合数学大数的阶乘、组合数动态规划方案数计数且不取模数论大数的幂运算、大数的GCD这道题属于DP计数不取模的情况。处理方式就是手写高精度加法。如果涉及乘法就要写高精度乘法复杂度会高很多。所以遇到高精度题先看运算类型如果只有加法那难度直接降一半。6.3 状态压缩与滚动数组的取舍DP数组如果开dp[L1][tot1]当L50tot100时是5100个高精度数。每个高精度数如果200位用int数组存就是5100×200×4字节≈4MB可以接受。但如果L1000那就是80MB可能超内存。这时候滚动数组就必要了。滚动数组的代价是丢失了中间状态无法回溯路径。但这道题只需要最终答案不需要回溯所以滚动数组是安全的。如果题目要求输出具体的方案比如输出所有合法字符串那就不能滚动必须保留完整DP表或者用其他方式记录路径。我个人在实际操作中的体会是先写非滚动版本确保逻辑正确然后再改成滚动数组优化。直接写滚动版本容易在数组下标上出错调试起来很痛苦。先正确再优化这个顺序不能反。6.4 字符集大小对算法的影响字符集大小直接影响两个地方Trie树的next数组大小和DP转移的循环次数。如果字符集是26那next[26]转移循环26次。如果字符集是256那next[256]每个节点占1KB100个节点就是100KB还好。但如果字符集是1000那每个节点4KB100个节点就是400KB加上DP数组内存就紧张了。这时候可以考虑用mapint,int来存转移只存存在的边。但map的查询是O(log n)比数组的O(1)慢。权衡一下如果字符集大但实际用到的字符少用map更省内存如果字符集大且大部分字符都用到那还是用数组内存换时间。这道题的字符集大小通常不会太大题目会给一个合理的范围所以直接用数组就行。但知道这个权衡遇到类似问题时能做出正确的选择。6.5 危险节点标记的另一种思路除了在BFS中下传危险标记还有一种思路在DP转移的时候沿着fail链检查是否有危险节点。但这样每次转移都要跳fail复杂度高。所以还是推荐在构建阶段就把危险标记下传好DP的时候直接O(1)判断。如果题目要求统计的是包含至少一个禁忌单词的字符串数量那可以用总数量减去不包含的数量。总数量是字符集大小^L也是一个高精度数需要高精度减法和幂运算。这就比这道题复杂了。所以看清楚题目要求的是不包含还是包含这决定了算法的方向。6.6 实际调试中的经验总结调试这类题目我通常分三步走第一步用最小的数据L1字符集大小2禁忌单词1个手动推演确认AC自动机的构建和DP的转移都正确。第二步用稍大的数据L5字符集大小3禁忌单词2个写暴力程序对比确认答案一致。第三步用大数据测试性能确认不超时、不超内存。这三步走下来基本能覆盖所有问题。最怕的是一上来就写完整代码然后发现答案不对又不知道错在哪。分步调试虽然看起来慢但实际上更快。另外代码的模块化很重要。把Trie插入、AC自动机构建、高精度加法、DP转移分成独立的函数每个函数单独测试。这样出错的时候能快速定位是哪个模块的问题。我见过很多人把所有逻辑写在一个main函数里出了错只能一行行看效率极低。最后再分享一个小技巧如果实在找不到bug可以把AC自动机的每个节点的next、fail、danger打印出来和手动构建的结果对比。很多时候问题就出在某个节点的fail指针指向了错误的位置导致危险标记下传错误最终答案偏大或偏小。这个方法虽然笨但非常有效。