1. 从一道经典题看AC自动机与动态规划的深度结合最近在整理一些算法竞赛的经典题目POJ 1625 “Censored!” 这道题又一次进入了我的视野。它绝对算得上是AC自动机Aho-Corasick Automaton与动态规划Dynamic Programming结合应用的“里程碑”式题目更因其对“大数运算”的硬性要求成为了检验选手综合能力的一块试金石。很多朋友在初次接触时往往卡在状态转移的细节或者大数处理的繁琐上感觉思路清晰但就是写不对。今天我就结合自己多次实现和教学的经验把这题的“里里外外”彻底拆解清楚不仅告诉你“怎么做”更要讲明白“为什么这么做”以及那些容易掉进去的坑。简单来说这道题的核心场景是给你一个包含N个字符的字母表比如{‘A’ ‘B’ ‘C’}一个包含M个禁止模式串Forbidden Patterns的字典要求你计算出所有长度为L的、由给定字母表构成的字符串中不包含任何禁止模式串作为子串的字符串有多少个。这里的“不包含”是指你不能从新生成的字符串中连续截取一段使得这段字符串恰好等于字典里的某个模式串。这本质上是一个在受限字符集上、带有“禁忌”条件的字符串计数问题。为什么说它经典因为它完美串联了三个关键知识点AC自动机用于高效处理多模式串匹配构建出字符串生成的“安全状态转移图”动态规划基于这个状态图进行精确的计数而大数运算则是因为结果可能极其庞大远超标准数据类型的表示范围必须手动处理高精度整数。这三个环节环环相扣缺一不可任何一个环节的理解偏差或实现疏忽都会导致全盘皆输。下面我们就一步步深入。2. 问题核心为什么是AC自动机DP在解决计数问题尤其是字符串计数问题时我们最朴素的想法可能是回溯DFS生成所有字符串并检查。但长度L动辄几十上百字母表大小N也可能达到几十搜索空间是N^L这显然是不可行的。动态规划是优化这类计数问题的利器关键在于找到合适的“状态”来表征我们构建字符串的过程。一个很自然的想法是用dp[i][j]表示我们构建了长度为i的字符串并且这个字符串的后缀恰好是字典中第j个模式串。但这个状态定义有问题首先后缀可能匹配多个模式串比如模式串有AB和BAB后缀AB同时是AB本身和BAB的后缀其次我们关心的不是“匹配了哪个”而是“是否匹配了任何一个”。状态会变得非常复杂。这时AC自动机就登场了。它的核心价值在于将所有的模式串构建成一棵Trie树并通过失败指针Fail Pointer将其连接成一个确定有限状态自动机DFA。在这个自动机里每个节点代表一个“状态”这个状态的含义是当前已构建字符串的最长后缀与Trie树中某个前缀的匹配情况。更具体地说从根节点开始读入一个字符就沿着Trie边或失败指针转移到一个新节点。这个新节点代表了加入新字符后新字符串所有后缀中在Trie里能找到的最长前缀。那么AC自动机的节点天然就是我们DP所需要的完美状态dp[i][u]可以定义为构建了长度为i的字符串并且使得该字符串在AC自动机中恰好转移到节点u的方案数。注意节点u蕴含了当前字符串的所有后缀信息。为什么这个状态是可行的因为AC自动机的转移是确定性的。给定当前状态节点和下一个输入字符我们可以唯一确定下一个状态。这完美契合了DP的“无后效性”原则——未来的发展只依赖于当前状态而与如何达到当前状态的路径无关。我们要确保最终的字符串不包含禁止串等价于在DP过程中永远不能转移到某个“标记为模式串结尾”的节点即AC自动机中的危险节点或终止节点。一旦转移到这样的节点就意味着我们刚刚构建的字符串的某个后缀完整地匹配了一个禁止模式串。所以解题的主干逻辑就清晰了构建AC自动机将所有禁止模式串插入Trie树构建失败指针并标记终止节点如果某个节点是某个模式串的结尾或者其失败指针指向的节点是终止节点那么它也是终止节点。这是关键因为如果“he”是禁止词那么“she”的后缀“he”也匹配了禁止词。DP状态转移初始化dp[0][0] 1长度为0在根节点。对于长度i从0到L-1遍历所有非终止节点u对于字母表中的每个字符c计算从节点u输入c后到达的节点v通过AC自动机的next转移函数。如果v不是终止节点那么dp[i1][v] dp[i][u]。统计结果最终所有dp[L][u]其中u为非终止节点的和就是所求的合法字符串总数。这个框架是理解本题的基石。接下来我们要深入每个环节的魔鬼细节。2.1 AC自动机构建中的关键终止标记的传递这是第一个容易出错的地方。在标准的AC自动机用于多模式匹配时我们通常只标记模式串的结尾节点。但在本题用于DP过滤时我们必须进行“终止标记的传递”。原因在于失败指针的含义如果节点u的失败指针指向节点fail[u]那么以节点u为结尾的字符串的后缀等同于以节点fail[u]为结尾的字符串。如果fail[u]是一个终止节点代表某个禁止串的结尾那么意味着当前字符串的某个后缀虽然不是从根节点开始的完整路径也构成了一个禁止串。因此节点u也必须被视为“危险”的终止节点。具体操作在BFS构建失败指针的过程中当为当前节点u的子节点v设置失败指针fail[v] next[fail[u]][ch]后需要立即检查flag[v] flag[v] || flag[fail[v]]。这里flag[x]为真表示节点x是终止节点。这样就能确保所有“隐含”包含禁止串的节点都被正确标记。一个简单的例子禁止串为{“he” “she”}。在Trie树中“she”的‘e’节点本身是“she”的结尾。同时它的失败指针会指向“he”的‘e’节点而“he”的‘e’节点是终止节点。因此“she”的‘e’节点通过flag[fail[v]]也会被标记为终止节点。这看起来是重复标记但逻辑上是正确的。实际上更常见且高效的做法是在构建完整个AC自动机后再进行一次拓扑序的传递或者直接在查询/转移函数中当沿着失败指针回溯时检查终止标记。但在DP的预处理中我们通常选择在构建阶段就完成所有终止标记的预处理得到一个布尔数组danger[u]这样在DP转移时只需要O(1)的判断。我的经验是在构建AC自动机的build()函数中在BFS设置完fail[v]后立刻执行danger[v] | danger[fail[v]]。这样得到的danger数组才是最终用于DP判断的“安全状态表”。2.2 DP转移的优化预处理转移矩阵在朴素的DP转移中对于每个状态(i, u)和每个字符c我们都需要调用一次AC自动机的转移函数next_state(u, c)。这个函数可能需要沿着失败指针回溯在最坏情况下是O(模式串总长度)。对于L较大如50、状态数AC自动机节点数设为S较多、字母表大小N较大的情况这个O(L * S * N * 转移成本)的复杂度可能成为瓶颈。一个非常有效的优化是预处理一个二维转移矩阵trans[u][c]。其中u是节点编号c是字母表字符映射后的整数0~N-1。trans[u][c]的值就是从节点u输入字符c后最终到达的节点v。这个预处理只需要对所有节点u和所有字符c执行一次next_state(u, c)并存储结果即可复杂度为O(S * N * 转移成本)。在后续DP的双重循环中转移操作就变成了O(1)的数组查找v trans[u][c]。这个优化将DP的核心循环复杂度从O(L * S * N * K)K为平均转移成本降低到了O(L * S * N)对于本题的规模提升非常明显。在实现时我们可以用一个二维数组int trans[MAX_NODE][MAX_ALPHABET]来存储。这里有一个实现技巧预处理trans矩阵时可以直接使用构建好的next数组和fail指针。标准的next_state函数逻辑如下int next_state(int u, int ch) { while (u !next[u][ch]) u fail[u]; // 如果当前节点没有ch边则沿fail回溯 u next[u][ch]; // 此时u要么是根要么有ch边 return u; }在预处理时我们对每个u和ch调用这个函数将结果存入trans[u][ch]。注意对于next[u][ch]存在的情况可以直接赋值避免重复回溯但为了代码清晰和正确性统一调用next_state是更稳妥的做法。3. 大数处理不可或缺的“麻烦”即使N2字母表只有两个字符L50合法字符串的数量也可能是一个天文数字远远超过long long甚至__int128的表示范围。因此大数高精度整数运算是本题的强制要求。很多AC自动机和DP都写对了但最后倒在大数实现上的情况比比皆是。我们需要实现一个大数类或结构体至少支持初始化、加法和输出。由于本题只涉及加法状态累加和最终的十进制输出相对简单。但即便如此也有几个细节需要注意。3.1 大数的内部表示与加法最常见的内部表示是用一个数组或vectorint按十进制从低位到高位存储每一位数字。例如数字12345存储为[54321]。加法就是模拟竖式加法注意处理进位。struct BigInt { vectorint digits; // 低位在前 BigInt() { digits.push_back(0); } BigInt(int num) { // 用int初始化 if (num 0) digits.push_back(0); while (num) { digits.push_back(num % 10); num / 10; } } void add(const BigInt other) { int carry 0; int max_len max(digits.size(), other.digits.size()); digits.resize(max_len, 0); for (int i 0; i max_len; 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); // 去除前导零除了数字0本身 while (digits.size() 1 digits.back() 0) digits.pop_back(); } // ... 输出函数 };在DP中我们的状态数组dp[i][u]的类型就从long long变成了BigInt。初始化dp[0][0] BigInt(1)。转移时调用dp[i1][v].add(dp[i][u])。3.2 性能与内存考量使用vector动态存储每一位每次加法都可能涉及内存分配和拷贝当状态数S和长度L较大时可能会有性能问题。一个优化点是预先为所有dp[i][u]分配好大数对象避免在循环中频繁构造和析构。我们可以使用二维数组vectorvectorBigInt dp(L1 vectorBigInt(S))。在加法时直接操作已存在的对象。另一个更高效的策略是使用压位。十进制每位存储0-9一个int可以存储更多信息。例如可以用BASE10000或1000000000作为基数这样每个数组元素存储9位或10位十进制数可以大大减少数组长度和加法次数。输出时也需要相应调整。对于本题如果L不超过50N不超过50用十进制直接存储通常也能通过但压位是更专业的做法。一个容易忽略的坑大数的默认构造函数和清零。在DP迭代每一层i时我们需要将dp[i1][...]全部清零然后再进行累加。如果BigInt类没有方便的清零操作就需要重新赋值为BigInt(0)。一种做法是在DP循环内部对于每个i先初始化dp[i1][v]为0或者使用两个二维数组滚动每次清空下一个数组。4. 完整实现流程与代码骨架将以上所有部分串联起来我们可以梳理出完整的实现步骤。这里我提供一个清晰的C代码骨架并标注关键点。4.1 数据结构定义与全局变量#include iostream #include vector #include queue #include cstring #include string #include map using namespace std; const int MAX_NODE 110; // 节点数上限根据模式串总长度设定 const int MAX_ALPHABET 55; // 字母表大小上限 int N M L; // 字母表大小 模式串数量 目标字符串长度 mapchar int charToId; // 将字母表字符映射为0~N-1的整数 // AC自动机部分 int next[MAX_NODE][MAX_ALPHABET]; // Trie树转移 int fail[MAX_NODE]; bool danger[MAX_NODE]; // 标记终止节点危险节点 int nodeCount; // 当前节点数 // DP与大数部分 struct BigInt { /* 如前文定义 */ }; vectorvectorBigInt dp; // dp[长度][状态] int trans[MAX_NODE][MAX_ALPHABET]; // 预处理转移矩阵4.2 AC自动机的实现void initAC() { memset(next[0] 0 sizeof(next[0])); fail[0] 0; danger[0] false; nodeCount 1; } void insert(const string pattern) { int u 0; for (char ch : pattern) { int c charToId[ch]; if (!next[u][c]) { memset(next[nodeCount] 0 sizeof(next[nodeCount])); danger[nodeCount] false; next[u][c] nodeCount; } u next[u][c]; } danger[u] true; // 标记模式串结尾为危险节点 } void build() { queueint q; // 初始化第一层节点的失败指针为根(0) for (int c 0; c N; c) { int v next[0][c]; if (v) { fail[v] 0; q.push(v); } } // BFS构建失败指针 while (!q.empty()) { int u q.front(); q.pop(); // 关键传递危险标记 if (danger[fail[u]]) { danger[u] true; } for (int c 0; c N; c) { int v next[u][c]; if (v) { fail[v] next[fail[u]][c]; // 再次传递因为fail[v]刚确定它的danger标记可能影响v if (danger[fail[v]]) { danger[v] true; } q.push(v); } else { // 路径压缩将不存在的边指向失败指针的下一个状态 next[u][c] next[fail[u]][c]; } } } } void preprocessTrans() { for (int u 0; u nodeCount; u) { for (int c 0; c N; c) { int state u; // 这里可以直接利用构建好的next数组已进行路径压缩 // 所以 next_state 简化为state next[state][c]; // 但为了清晰我们实现一个即使没有路径压缩也能工作的版本 int v u; while (v !next[v][c]) v fail[v]; v next[v][c]; trans[u][c] v; } } }注意在build()函数中我采用了“路径压缩”的优化即next[u][c] next[fail[u]][c]当next[u][c]不存在时。这使我们在查询next_state时无需循环直接访问next[u][c]即可。此时preprocessTrans可以简化为trans[u][c] next[u][c]。两种方式都是正确的路径压缩更高效。4.3 动态规划与大数统计int main() { // 读入 N M L // 读入字母表字符串构建 charToId 映射 // 初始化AC自动机 initAC() // 读入M个模式串调用 insert() 插入 // 构建AC自动机 build() // 预处理转移矩阵 preprocessTrans() // 初始化DP数组 dp.assign(L 1 vectorBigInt(nodeCount BigInt(0))); dp[0][0] BigInt(1); // 长度为0在根节点方案数为1 for (int i 0; i L; i) { for (int u 0; u nodeCount; u) { if (danger[u]) continue; // 当前状态已是危险状态不可能从此开始转移 if (dp[i][u].digits.size() 1 dp[i][u].digits[0] 0) continue; // 方案数为0跳过 for (int c 0; c N; c) { int v trans[u][c]; if (danger[v]) continue; // 转移到危险状态非法 dp[i 1][v].add(dp[i][u]); } } } // 统计结果 BigInt ans(0); for (int u 0; u nodeCount; u) { if (!danger[u]) { ans.add(dp[L][u]); } } // 输出ans ans.print(); // 需要实现BigInt的打印函数从高位到低位输出digits return 0; }5. 边界条件、调试与性能优化即使有了清晰的框架实际编码中还是会遇到各种问题。这里分享几个调试经验和优化技巧。5.1 边界条件与特殊输入字母表映射题目给的字母表可能不是连续的‘A’-‘Z’可能是任意ASCII字符。必须用map或数组建立字符到索引(0~N-1)的映射。这是所有后续操作的基础映射错了全盘皆错。空模式串题目应该不会给空串但理论上如果给了插入Trie时应将根节点标记为危险这样任何字符串都不合法结果应为0。L0长度为0的字符串只有一个空串。只要根节点不是危险节点即没有空禁止串结果应为1。我们的DP初始化dp[0][0]1能正确处理。大数输出前导零数字0应输出“0”。确保你的BigInt输出函数能处理digits只有一位且为0的情况。节点数估算模式串总长度不超过某个值如100但AC自动机节点数可能略多于总长度。保险起见MAX_NODE可以设大一点如150。5.2 调试技巧从小规模数据与打印状态入手当程序结果不对时不要急于看大数据。构造极小数据例如字母表{AB}禁止串{“A”}求长度L2的合法串。合法串应为{“BB” “BA”}不对“BA”以‘A’结尾包含“A”。实际上只有“BB”。手算结果是1。用程序跑看结果是否为1。打印AC自动机结构输出每个节点的fail指针、danger标记以及trans矩阵。检查危险标记是否正确传递。例如禁止串{“he” “she”}检查“she”路径上的‘e’节点是否被标记为危险。打印DP表对于小规模L如3打印每一层的dp[i][u]值。看方案数是否按预期转移。这能帮你发现状态转移或危险判断的逻辑错误。验证大数加法单独测试大数类确保加法正确特别是进位和多个大数累加的情况。5.3 性能优化点滚动数组DP数组dp[i][u]只依赖于dp[i-1][...]因此可以用两个一维数组dp_now和dp_next滚动节省大量内存。这对于节点数多、大数对象大的情况很有用。vectorBigInt dp_now(nodeCount BigInt(0)) dp_next(nodeCount BigInt(0)); dp_now[0] BigInt(1); for (int i 0; i L; i) { fill(dp_next.begin() dp_next.end() BigInt(0)); // 清空下一层 for (int u 0; u nodeCount; u) { if (danger[u] || dp_now[u].isZero()) continue; for (int c 0; c N; c) { int v trans[u][c]; if (!danger[v]) { dp_next[v].add(dp_now[u]); } } } swap(dp_now dp_next); }大数加法的内联与引用传递在DP的核心循环中大数加法被频繁调用。确保add函数参数使用const BigInt引用避免拷贝。如果编译器支持可以考虑将函数定义在类内默认内联。减少不必要的判断在DP循环中先判断if (dp_now[u].isZero())可以跳过大量无效状态。实现isZero()方法检查digits是否只有一位且为0。字符映射优化如果字母表是连续字符如‘A’-‘Z’可以直接用ch - ‘A’作为索引比map查找更快。但题目未明确说明用map更安全。6. 从本题延伸AC自动机与DP的更多应用场景POJ 1625 提供了一个经典的“字符串计数禁忌模式”的模板。掌握它之后你可以解决一大类问题。其变体包括概率或期望问题不再是计数而是每个字符有特定的出现概率求合法字符串的概率和或期望长度。此时DP值从大数变为浮点数或分数转移时乘以概率即可。包含至少一个模式串求包含至少一个禁止串的字符串数量。可以用总数N^L减去完全不包含的数量即本题结果。或者修改DP状态增加一维表示“是否已经包含过模式串”。求最大/最小权值每个字符有一个权值求合法字符串的最大/最小总权值。DP状态值从计数变为权值转移时做max或min操作。与矩阵快速幂结合当L非常大如1e9时逐层DP不可行。我们可以将状态转移关系表示为矩阵M其中M[u][v]表示从状态u通过一个字符转移到状态v的方案数如果v安全。那么dp[L] dp[0] * (M^L)。利用矩阵快速幂可以在O(S^3 log L)时间内求解其中S是状态数AC自动机节点数。这是处理超大L的通用方法。理解AC自动机作为状态机DP在其上进行状态转移的这一核心思想远比AC一道题目更重要。它揭示了将字符串匹配这种“过程性”问题转化为在有限状态上进行“计数”或“优化”问题的通用思路。下次当你遇到需要处理多个模式串的字符串问题时不妨先想想能不能建一个AC自动机把它的节点作为状态把问题转化成一个图上的DP问题。这个思维转换才是解决此类问题的钥匙。 
长河君 · 2026/8/29 2:52:11 · 阅读 1.2k AC自动机与动态规划结合：解决POJ 1625字符串计数问题
1. 从一道经典题看AC自动机与动态规划的深度结合最近在整理一些算法竞赛的经典题目POJ 1625 “Censored!” 这道题又一次进入了我的视野。它绝对算得上是AC自动机Aho-Corasick Automaton与动态规划Dynamic Programming结合应用的“里程碑”式题目更因其对“大数运算”的硬性要求成为了检验选手综合能力的一块试金石。很多朋友在初次接触时往往卡在状态转移的细节或者大数处理的繁琐上感觉思路清晰但就是写不对。今天我就结合自己多次实现和教学的经验把这题的“里里外外”彻底拆解清楚不仅告诉你“怎么做”更要讲明白“为什么这么做”以及那些容易掉进去的坑。简单来说这道题的核心场景是给你一个包含N个字符的字母表比如{‘A’ ‘B’ ‘C’}一个包含M个禁止模式串Forbidden Patterns的字典要求你计算出所有长度为L的、由给定字母表构成的字符串中不包含任何禁止模式串作为子串的字符串有多少个。这里的“不包含”是指你不能从新生成的字符串中连续截取一段使得这段字符串恰好等于字典里的某个模式串。这本质上是一个在受限字符集上、带有“禁忌”条件的字符串计数问题。为什么说它经典因为它完美串联了三个关键知识点AC自动机用于高效处理多模式串匹配构建出字符串生成的“安全状态转移图”动态规划基于这个状态图进行精确的计数而大数运算则是因为结果可能极其庞大远超标准数据类型的表示范围必须手动处理高精度整数。这三个环节环环相扣缺一不可任何一个环节的理解偏差或实现疏忽都会导致全盘皆输。下面我们就一步步深入。2. 问题核心为什么是AC自动机DP在解决计数问题尤其是字符串计数问题时我们最朴素的想法可能是回溯DFS生成所有字符串并检查。但长度L动辄几十上百字母表大小N也可能达到几十搜索空间是N^L这显然是不可行的。动态规划是优化这类计数问题的利器关键在于找到合适的“状态”来表征我们构建字符串的过程。一个很自然的想法是用dp[i][j]表示我们构建了长度为i的字符串并且这个字符串的后缀恰好是字典中第j个模式串。但这个状态定义有问题首先后缀可能匹配多个模式串比如模式串有AB和BAB后缀AB同时是AB本身和BAB的后缀其次我们关心的不是“匹配了哪个”而是“是否匹配了任何一个”。状态会变得非常复杂。这时AC自动机就登场了。它的核心价值在于将所有的模式串构建成一棵Trie树并通过失败指针Fail Pointer将其连接成一个确定有限状态自动机DFA。在这个自动机里每个节点代表一个“状态”这个状态的含义是当前已构建字符串的最长后缀与Trie树中某个前缀的匹配情况。更具体地说从根节点开始读入一个字符就沿着Trie边或失败指针转移到一个新节点。这个新节点代表了加入新字符后新字符串所有后缀中在Trie里能找到的最长前缀。那么AC自动机的节点天然就是我们DP所需要的完美状态dp[i][u]可以定义为构建了长度为i的字符串并且使得该字符串在AC自动机中恰好转移到节点u的方案数。注意节点u蕴含了当前字符串的所有后缀信息。为什么这个状态是可行的因为AC自动机的转移是确定性的。给定当前状态节点和下一个输入字符我们可以唯一确定下一个状态。这完美契合了DP的“无后效性”原则——未来的发展只依赖于当前状态而与如何达到当前状态的路径无关。我们要确保最终的字符串不包含禁止串等价于在DP过程中永远不能转移到某个“标记为模式串结尾”的节点即AC自动机中的危险节点或终止节点。一旦转移到这样的节点就意味着我们刚刚构建的字符串的某个后缀完整地匹配了一个禁止模式串。所以解题的主干逻辑就清晰了构建AC自动机将所有禁止模式串插入Trie树构建失败指针并标记终止节点如果某个节点是某个模式串的结尾或者其失败指针指向的节点是终止节点那么它也是终止节点。这是关键因为如果“he”是禁止词那么“she”的后缀“he”也匹配了禁止词。DP状态转移初始化dp[0][0] 1长度为0在根节点。对于长度i从0到L-1遍历所有非终止节点u对于字母表中的每个字符c计算从节点u输入c后到达的节点v通过AC自动机的next转移函数。如果v不是终止节点那么dp[i1][v] dp[i][u]。统计结果最终所有dp[L][u]其中u为非终止节点的和就是所求的合法字符串总数。这个框架是理解本题的基石。接下来我们要深入每个环节的魔鬼细节。2.1 AC自动机构建中的关键终止标记的传递这是第一个容易出错的地方。在标准的AC自动机用于多模式匹配时我们通常只标记模式串的结尾节点。但在本题用于DP过滤时我们必须进行“终止标记的传递”。原因在于失败指针的含义如果节点u的失败指针指向节点fail[u]那么以节点u为结尾的字符串的后缀等同于以节点fail[u]为结尾的字符串。如果fail[u]是一个终止节点代表某个禁止串的结尾那么意味着当前字符串的某个后缀虽然不是从根节点开始的完整路径也构成了一个禁止串。因此节点u也必须被视为“危险”的终止节点。具体操作在BFS构建失败指针的过程中当为当前节点u的子节点v设置失败指针fail[v] next[fail[u]][ch]后需要立即检查flag[v] flag[v] || flag[fail[v]]。这里flag[x]为真表示节点x是终止节点。这样就能确保所有“隐含”包含禁止串的节点都被正确标记。一个简单的例子禁止串为{“he” “she”}。在Trie树中“she”的‘e’节点本身是“she”的结尾。同时它的失败指针会指向“he”的‘e’节点而“he”的‘e’节点是终止节点。因此“she”的‘e’节点通过flag[fail[v]]也会被标记为终止节点。这看起来是重复标记但逻辑上是正确的。实际上更常见且高效的做法是在构建完整个AC自动机后再进行一次拓扑序的传递或者直接在查询/转移函数中当沿着失败指针回溯时检查终止标记。但在DP的预处理中我们通常选择在构建阶段就完成所有终止标记的预处理得到一个布尔数组danger[u]这样在DP转移时只需要O(1)的判断。我的经验是在构建AC自动机的build()函数中在BFS设置完fail[v]后立刻执行danger[v] | danger[fail[v]]。这样得到的danger数组才是最终用于DP判断的“安全状态表”。2.2 DP转移的优化预处理转移矩阵在朴素的DP转移中对于每个状态(i, u)和每个字符c我们都需要调用一次AC自动机的转移函数next_state(u, c)。这个函数可能需要沿着失败指针回溯在最坏情况下是O(模式串总长度)。对于L较大如50、状态数AC自动机节点数设为S较多、字母表大小N较大的情况这个O(L * S * N * 转移成本)的复杂度可能成为瓶颈。一个非常有效的优化是预处理一个二维转移矩阵trans[u][c]。其中u是节点编号c是字母表字符映射后的整数0~N-1。trans[u][c]的值就是从节点u输入字符c后最终到达的节点v。这个预处理只需要对所有节点u和所有字符c执行一次next_state(u, c)并存储结果即可复杂度为O(S * N * 转移成本)。在后续DP的双重循环中转移操作就变成了O(1)的数组查找v trans[u][c]。这个优化将DP的核心循环复杂度从O(L * S * N * K)K为平均转移成本降低到了O(L * S * N)对于本题的规模提升非常明显。在实现时我们可以用一个二维数组int trans[MAX_NODE][MAX_ALPHABET]来存储。这里有一个实现技巧预处理trans矩阵时可以直接使用构建好的next数组和fail指针。标准的next_state函数逻辑如下int next_state(int u, int ch) { while (u !next[u][ch]) u fail[u]; // 如果当前节点没有ch边则沿fail回溯 u next[u][ch]; // 此时u要么是根要么有ch边 return u; }在预处理时我们对每个u和ch调用这个函数将结果存入trans[u][ch]。注意对于next[u][ch]存在的情况可以直接赋值避免重复回溯但为了代码清晰和正确性统一调用next_state是更稳妥的做法。3. 大数处理不可或缺的“麻烦”即使N2字母表只有两个字符L50合法字符串的数量也可能是一个天文数字远远超过long long甚至__int128的表示范围。因此大数高精度整数运算是本题的强制要求。很多AC自动机和DP都写对了但最后倒在大数实现上的情况比比皆是。我们需要实现一个大数类或结构体至少支持初始化、加法和输出。由于本题只涉及加法状态累加和最终的十进制输出相对简单。但即便如此也有几个细节需要注意。3.1 大数的内部表示与加法最常见的内部表示是用一个数组或vectorint按十进制从低位到高位存储每一位数字。例如数字12345存储为[54321]。加法就是模拟竖式加法注意处理进位。struct BigInt { vectorint digits; // 低位在前 BigInt() { digits.push_back(0); } BigInt(int num) { // 用int初始化 if (num 0) digits.push_back(0); while (num) { digits.push_back(num % 10); num / 10; } } void add(const BigInt other) { int carry 0; int max_len max(digits.size(), other.digits.size()); digits.resize(max_len, 0); for (int i 0; i max_len; 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); // 去除前导零除了数字0本身 while (digits.size() 1 digits.back() 0) digits.pop_back(); } // ... 输出函数 };在DP中我们的状态数组dp[i][u]的类型就从long long变成了BigInt。初始化dp[0][0] BigInt(1)。转移时调用dp[i1][v].add(dp[i][u])。3.2 性能与内存考量使用vector动态存储每一位每次加法都可能涉及内存分配和拷贝当状态数S和长度L较大时可能会有性能问题。一个优化点是预先为所有dp[i][u]分配好大数对象避免在循环中频繁构造和析构。我们可以使用二维数组vectorvectorBigInt dp(L1 vectorBigInt(S))。在加法时直接操作已存在的对象。另一个更高效的策略是使用压位。十进制每位存储0-9一个int可以存储更多信息。例如可以用BASE10000或1000000000作为基数这样每个数组元素存储9位或10位十进制数可以大大减少数组长度和加法次数。输出时也需要相应调整。对于本题如果L不超过50N不超过50用十进制直接存储通常也能通过但压位是更专业的做法。一个容易忽略的坑大数的默认构造函数和清零。在DP迭代每一层i时我们需要将dp[i1][...]全部清零然后再进行累加。如果BigInt类没有方便的清零操作就需要重新赋值为BigInt(0)。一种做法是在DP循环内部对于每个i先初始化dp[i1][v]为0或者使用两个二维数组滚动每次清空下一个数组。4. 完整实现流程与代码骨架将以上所有部分串联起来我们可以梳理出完整的实现步骤。这里我提供一个清晰的C代码骨架并标注关键点。4.1 数据结构定义与全局变量#include iostream #include vector #include queue #include cstring #include string #include map using namespace std; const int MAX_NODE 110; // 节点数上限根据模式串总长度设定 const int MAX_ALPHABET 55; // 字母表大小上限 int N M L; // 字母表大小 模式串数量 目标字符串长度 mapchar int charToId; // 将字母表字符映射为0~N-1的整数 // AC自动机部分 int next[MAX_NODE][MAX_ALPHABET]; // Trie树转移 int fail[MAX_NODE]; bool danger[MAX_NODE]; // 标记终止节点危险节点 int nodeCount; // 当前节点数 // DP与大数部分 struct BigInt { /* 如前文定义 */ }; vectorvectorBigInt dp; // dp[长度][状态] int trans[MAX_NODE][MAX_ALPHABET]; // 预处理转移矩阵4.2 AC自动机的实现void initAC() { memset(next[0] 0 sizeof(next[0])); fail[0] 0; danger[0] false; nodeCount 1; } void insert(const string pattern) { int u 0; for (char ch : pattern) { int c charToId[ch]; if (!next[u][c]) { memset(next[nodeCount] 0 sizeof(next[nodeCount])); danger[nodeCount] false; next[u][c] nodeCount; } u next[u][c]; } danger[u] true; // 标记模式串结尾为危险节点 } void build() { queueint q; // 初始化第一层节点的失败指针为根(0) for (int c 0; c N; c) { int v next[0][c]; if (v) { fail[v] 0; q.push(v); } } // BFS构建失败指针 while (!q.empty()) { int u q.front(); q.pop(); // 关键传递危险标记 if (danger[fail[u]]) { danger[u] true; } for (int c 0; c N; c) { int v next[u][c]; if (v) { fail[v] next[fail[u]][c]; // 再次传递因为fail[v]刚确定它的danger标记可能影响v if (danger[fail[v]]) { danger[v] true; } q.push(v); } else { // 路径压缩将不存在的边指向失败指针的下一个状态 next[u][c] next[fail[u]][c]; } } } } void preprocessTrans() { for (int u 0; u nodeCount; u) { for (int c 0; c N; c) { int state u; // 这里可以直接利用构建好的next数组已进行路径压缩 // 所以 next_state 简化为state next[state][c]; // 但为了清晰我们实现一个即使没有路径压缩也能工作的版本 int v u; while (v !next[v][c]) v fail[v]; v next[v][c]; trans[u][c] v; } } }注意在build()函数中我采用了“路径压缩”的优化即next[u][c] next[fail[u]][c]当next[u][c]不存在时。这使我们在查询next_state时无需循环直接访问next[u][c]即可。此时preprocessTrans可以简化为trans[u][c] next[u][c]。两种方式都是正确的路径压缩更高效。4.3 动态规划与大数统计int main() { // 读入 N M L // 读入字母表字符串构建 charToId 映射 // 初始化AC自动机 initAC() // 读入M个模式串调用 insert() 插入 // 构建AC自动机 build() // 预处理转移矩阵 preprocessTrans() // 初始化DP数组 dp.assign(L 1 vectorBigInt(nodeCount BigInt(0))); dp[0][0] BigInt(1); // 长度为0在根节点方案数为1 for (int i 0; i L; i) { for (int u 0; u nodeCount; u) { if (danger[u]) continue; // 当前状态已是危险状态不可能从此开始转移 if (dp[i][u].digits.size() 1 dp[i][u].digits[0] 0) continue; // 方案数为0跳过 for (int c 0; c N; c) { int v trans[u][c]; if (danger[v]) continue; // 转移到危险状态非法 dp[i 1][v].add(dp[i][u]); } } } // 统计结果 BigInt ans(0); for (int u 0; u nodeCount; u) { if (!danger[u]) { ans.add(dp[L][u]); } } // 输出ans ans.print(); // 需要实现BigInt的打印函数从高位到低位输出digits return 0; }5. 边界条件、调试与性能优化即使有了清晰的框架实际编码中还是会遇到各种问题。这里分享几个调试经验和优化技巧。5.1 边界条件与特殊输入字母表映射题目给的字母表可能不是连续的‘A’-‘Z’可能是任意ASCII字符。必须用map或数组建立字符到索引(0~N-1)的映射。这是所有后续操作的基础映射错了全盘皆错。空模式串题目应该不会给空串但理论上如果给了插入Trie时应将根节点标记为危险这样任何字符串都不合法结果应为0。L0长度为0的字符串只有一个空串。只要根节点不是危险节点即没有空禁止串结果应为1。我们的DP初始化dp[0][0]1能正确处理。大数输出前导零数字0应输出“0”。确保你的BigInt输出函数能处理digits只有一位且为0的情况。节点数估算模式串总长度不超过某个值如100但AC自动机节点数可能略多于总长度。保险起见MAX_NODE可以设大一点如150。5.2 调试技巧从小规模数据与打印状态入手当程序结果不对时不要急于看大数据。构造极小数据例如字母表{AB}禁止串{“A”}求长度L2的合法串。合法串应为{“BB” “BA”}不对“BA”以‘A’结尾包含“A”。实际上只有“BB”。手算结果是1。用程序跑看结果是否为1。打印AC自动机结构输出每个节点的fail指针、danger标记以及trans矩阵。检查危险标记是否正确传递。例如禁止串{“he” “she”}检查“she”路径上的‘e’节点是否被标记为危险。打印DP表对于小规模L如3打印每一层的dp[i][u]值。看方案数是否按预期转移。这能帮你发现状态转移或危险判断的逻辑错误。验证大数加法单独测试大数类确保加法正确特别是进位和多个大数累加的情况。5.3 性能优化点滚动数组DP数组dp[i][u]只依赖于dp[i-1][...]因此可以用两个一维数组dp_now和dp_next滚动节省大量内存。这对于节点数多、大数对象大的情况很有用。vectorBigInt dp_now(nodeCount BigInt(0)) dp_next(nodeCount BigInt(0)); dp_now[0] BigInt(1); for (int i 0; i L; i) { fill(dp_next.begin() dp_next.end() BigInt(0)); // 清空下一层 for (int u 0; u nodeCount; u) { if (danger[u] || dp_now[u].isZero()) continue; for (int c 0; c N; c) { int v trans[u][c]; if (!danger[v]) { dp_next[v].add(dp_now[u]); } } } swap(dp_now dp_next); }大数加法的内联与引用传递在DP的核心循环中大数加法被频繁调用。确保add函数参数使用const BigInt引用避免拷贝。如果编译器支持可以考虑将函数定义在类内默认内联。减少不必要的判断在DP循环中先判断if (dp_now[u].isZero())可以跳过大量无效状态。实现isZero()方法检查digits是否只有一位且为0。字符映射优化如果字母表是连续字符如‘A’-‘Z’可以直接用ch - ‘A’作为索引比map查找更快。但题目未明确说明用map更安全。6. 从本题延伸AC自动机与DP的更多应用场景POJ 1625 提供了一个经典的“字符串计数禁忌模式”的模板。掌握它之后你可以解决一大类问题。其变体包括概率或期望问题不再是计数而是每个字符有特定的出现概率求合法字符串的概率和或期望长度。此时DP值从大数变为浮点数或分数转移时乘以概率即可。包含至少一个模式串求包含至少一个禁止串的字符串数量。可以用总数N^L减去完全不包含的数量即本题结果。或者修改DP状态增加一维表示“是否已经包含过模式串”。求最大/最小权值每个字符有一个权值求合法字符串的最大/最小总权值。DP状态值从计数变为权值转移时做max或min操作。与矩阵快速幂结合当L非常大如1e9时逐层DP不可行。我们可以将状态转移关系表示为矩阵M其中M[u][v]表示从状态u通过一个字符转移到状态v的方案数如果v安全。那么dp[L] dp[0] * (M^L)。利用矩阵快速幂可以在O(S^3 log L)时间内求解其中S是状态数AC自动机节点数。这是处理超大L的通用方法。理解AC自动机作为状态机DP在其上进行状态转移的这一核心思想远比AC一道题目更重要。它揭示了将字符串匹配这种“过程性”问题转化为在有限状态上进行“计数”或“优化”问题的通用思路。下次当你遇到需要处理多个模式串的字符串问题时不妨先想想能不能建一个AC自动机把它的节点作为状态把问题转化成一个图上的DP问题。这个思维转换才是解决此类问题的钥匙。