从KMP到动态规划：解决“设计密码”算法题与状态机实战

1. 项目概述从一道经典算法题到现实世界的密码设计“设计密码”这个标题乍一看像是要讲如何创建一个强密码来保护账户安全。但在算法和编程竞赛的语境里它特指LeetCode上那道编号为1052的经典题目。这道题本身是一个动态规划问题但它背后所蕴含的思维模型却与我们日常设计系统、处理字符串匹配、乃至构思一个健壮的验证逻辑息息相关。我最初接触这道题时觉得它就是个纯粹的算法练习但在实际工作中反复遇到类似“状态机”、“模式匹配”、“避免子串出现”的需求后才真正体会到它的价值。它教会我们的不是背下一个解法而是如何将“禁止出现特定模式”这一约束转化为可计算、可遍历的系统状态这个思想在软件开发的很多场景下都能用上。简单来说这道题是这样的你需要构造一个长度为N的密码这个密码只能由小写字母组成。同时你会得到一个字符串T我们称之为“禁止串”。你的目标是设计出所有可能的密码并且确保这个密码中不包含禁止串T作为其子串。最终我们需要输出所有满足条件的密码数量。这听起来像是一个排列组合问题但字符串T的存在使得密码字符之间产生了强烈的依赖关系——下一个字符的选择会受到前面已构造部分是否已经“接近”形成禁止串的影响。这就是动态规划大显身手的地方。无论你是正在准备技术面试的求职者还是对字符串处理、状态机设计感兴趣的开发者理解这个问题都能带来切实的提升。它不仅锻炼你定义状态、推导转移方程的能力更能让你深刻理解KMP算法中“最长公共前后缀”概念的精妙复用。接下来我会带你从问题本质出发一步步拆解思路给出清晰的实现方案并分享一些我在调试和优化过程中的实战心得。2. 核心思路拆解状态机与动态规划的融合要解决这个问题暴力枚举所有长度为N的小写字母字符串共有26^N种可能然后逐个检查是否包含子串T在N稍大时比如N10就完全不可行。我们必须找到更聪明的方法。核心的突破口在于我们并不关心密码具体是什么只关心它在构造过程中与禁止串T的匹配程度。这种“匹配程度”可以用一个状态来表示。2.1 为什么是状态机想象一下你正在一个字符一个字符地构造密码。同时你手里拿着禁止串T像一把尺子一样在已经构造好的密码末尾进行比对。这个比对的过程就是一个状态转移的过程。我们定义状态j(0 j M其中M是禁止串T的长度) 表示当前已构造的密码后缀与禁止串T的前缀匹配的长度为j。换句话说如果我们把当前密码的末尾和T的开头对齐最多能连续匹配上j个字符。状态j 0意味着当前密码的末尾与T的开头第一个字符都不匹配。这是最“安全”的状态离形成禁止子串最远。状态j k(0 k M)意味着当前密码的末尾已经匹配上了T的前k个字符。这时我们处于“危险”的边缘下一个字符的选择必须非常小心否则就可能完成匹配达到状态M即形成了禁止子串。状态j M这意味着我们已经完整匹配了禁止串T即密码中包含了T作为子串。这个状态是我们需要避免的非法状态。我们的目标就是在构造长度为N的密码过程中始终避免进入状态M。每一个新添加的字符都会引起状态的转移。这个转移规则正是KMP算法中核心的“失配函数”或“next数组”所描述的。2.2 动态规划状态定义有了状态机的概念我们就可以用动态规划来计数了。我们定义dp[i][j]表示构造了长度为i的密码且当前处于状态j即密码后缀与T的前缀匹配长度为j的方案数量。其中i的范围是[0, N]表示密码的当前长度。j的范围是[0, M-1]因为我们禁止达到状态M一旦达到就说明密码非法不计入方案。初始状态dp[0][0] 1。这表示一个长度为0的空密码它自然匹配T的长度为0有1种方案就是空本身。最终答案我们需要所有长度为N且状态不为M的密码。所以答案是sum(dp[N][j])其中j从0到M-1。2.3 状态转移方程推导这是最精妙的部分。假设我们已经计算好了dp[i][j]即长度为i、状态为j的方案数。现在我们要添加第i1个字符可以是26个小写字母中的任意一个新的状态会变成多少设我们添加的字符为c。我们需要计算在原有匹配长度为j的基础上加上字符c后新的匹配长度next_j是多少。这个过程完全就是KMP算法中匹配过程的一个步骤。我们可以模拟这个匹配过程如果c T[j]那么匹配长度可以直接增加1即next_j j 1。如果c ! T[j]那么我们就不能直接匹配了。这时我们需要利用KMP的思想回溯到一个更短的匹配位置。这个位置就是KMP的next数组或者称为“部分匹配表”里定义的值。我们记k next[j]这里的next[j]表示当在T的第j位失配时应该跳转到T的哪个位置继续尝试匹配。然后我们再看c是否等于T[k]重复这个过程直到匹配成功或者回到0。注意这里有一个关键的实现技巧。我们可以预处理一个二维数组auto[m][26]。auto[j][c]表示当前状态为j时下一个输入字符是c时将会转移到的下一个状态next_j。这个预处理过程就是一次对KMP状态机的构建。有了它我们在动态规划转移时就可以在O(1)时间内通过查表得到next_j而不需要在每次转移时都模拟KMP的跳转过程极大提升了效率。因此状态转移方程可以描述为 对于每个状态dp[i][j]对于26个可能的字符c用0-25表示查表得到新状态next_j auto[j][c]。如果next_j M即没有形成完整的禁止串那么我们就可以进行转移dp[i1][next_j] dp[i][j]。如果next_j M则意味着添加字符c后形成了禁止串这个转移路径是无效的我们直接舍弃。2.4 复杂度分析时间复杂度预处理auto数组需要 O(M * 26)。动态规划过程需要遍历i(0~N)j(0~M-1) 和 26个字符所以是 O(N * M * 26)。由于M通常远小于N且26是常数所以可以认为是 O(N * M)。空间复杂度dp数组是 O(N * M)但我们可以发现dp[i1]只依赖于dp[i]因此可以使用滚动数组优化到 O(M)。auto数组是 O(M * 26)。3. 完整实现与代码详解理解了核心思想后我们来看具体的代码实现。我会用Python作为示例语言因为它表达清晰易于理解。代码将包含详细的注释并分为几个关键步骤。3.1 步骤一构建KMP的next数组next数组为避免与Python关键字冲突常命名为fail或lps是KMP算法的核心。next[j]表示字符串T的前缀T[0:j]长度为j中最长的相等真前缀和真后缀的长度。def build_kmp_next(pattern: str): 构建KMP算法的next数组有时称为lps数组。 m len(pattern) next_arr [0] * m # next[0] 始终为0 j 0 # 指向前缀的末尾 for i in range(1, m): # i指向后缀的末尾 # 当字符不匹配时利用已经计算好的next数组回退j while j 0 and pattern[i] ! pattern[j]: j next_arr[j - 1] # 如果字符匹配则最长公共前后缀长度增加 if pattern[i] pattern[j]: j 1 next_arr[i] j return next_arr实操心得构建next数组时循环变量i从1开始因为长度为1的子串没有真前缀和真后缀。内层的while循环是理解的关键它体现了“利用已知信息避免重复匹配”的KMP思想。务必亲手模拟一下这个过程比如对模式串ababc计算next数组结果是[0, 0, 1, 2, 0]。3.2 步骤二预处理状态转移表auto这是将KMP思想融入动态规划的关键一步。auto[j][c]定义了状态机。def build_automaton(pattern: str): 构建状态自动机。返回自动机转移表auto。 m len(pattern) next_arr build_kmp_next(pattern) # auto[j][c]状态j下遇到字符c映射为0-25时转移到的下一个状态 auto [[0] * 26 for _ in range(m)] for state in range(m): # 当前状态 for c_idx in range(26): # 尝试所有可能的字符 c chr(ord(a) c_idx) if state m and c pattern[state]: # 如果字符匹配状态前进 new_state state 1 else: # 如果不匹配则回退到next[state-1]的状态并继续尝试匹配字符c # 注意处理state0的情况 new_state state while new_state 0 and c ! pattern[new_state]: new_state next_arr[new_state - 1] if c pattern[new_state]: new_state 1 # 如果循环结束仍不匹配new_state就是0 auto[state][c_idx] new_state return auto注意事项在计算auto表时内层循环对每个状态state和每个字符c都模拟了KMP匹配过程。虽然看起来是三重循环state, c_idx, 可能的while回退但平摊分析下来每个字符c对于每个state的匹配过程与KMP算法本身复杂度一致总复杂度仍是 O(M * 26)。这个预处理是值得的它让后续的DP转移变得极其简单高效。3.3 步骤三动态规划计数有了自动机动态规划的过程就非常直观了。def design_password_count(N: int, forbidden: str) - int: 计算长度为N且不包含子串forbidden的密码总数。 MOD 10**9 7 # 通常题目要求对结果取模防止溢出 m len(forbidden) if m 0: # 如果禁止串为空那么任何密码都包含空串方案数为0除非题目特别定义 # 根据常见题意通常认为空串是任何字符串的子串所以返回0。 # 但有些题目可能规定N1且空串不算。这里按返回0处理具体需看题。 return 0 if N 0: # 长度为0的密码只有空串只要禁止串不是空串它就合法。 return 1 if m 0 else 0 auto build_automaton(forbidden) # dp[j] 表示当前长度下处于状态j的方案数。使用滚动数组。 dp [0] * m dp[0] 1 # 初始状态长度为0匹配长度为0有1种方案空密码 for i in range(N): # 构造密码的每一位 new_dp [0] * m for state in range(m): # 遍历所有当前可能的状态 if dp[state] 0: continue current_count dp[state] # 尝试添加26个可能的字符 for c_idx in range(26): next_state auto[state][c_idx] if next_state m: # 如果新状态没有形成完整禁止串 new_dp[next_state] (new_dp[next_state] current_count) % MOD # 如果 next_state m则丢弃这个转移 dp new_dp # 滚动到下一层 # 最终所有长度为N且状态j m 的方案都是合法的 result sum(dp) % MOD return result代码细节解析取模由于方案数可能巨大26^N题目通常要求对10^97取模。我们在每次加法后立即取模避免中间结果溢出。滚动数组注意dp和new_dp的用法。dp代表长度为i时的状态方案数new_dp代表长度为i1时的状态方案数。每一轮迭代后用new_dp覆盖dp。这节省了大量空间。状态转移最内层循环对于当前状态state的dp[state]种方案每一种都可以通过添加26个字符中的任意一个转移到新的状态next_state。只要next_state不等于m即没有匹配完禁止串我们就将方案数累加到new_dp[next_state]中。边界处理对N0和forbidden为空串的情况进行了处理。这是良好的编程习惯能避免 corner case 错误。3.4 步骤四测试与验证写完代码一定要测试。我们可以用一些简单例子来验证。# 测试用例 if __name__ __main__: # 例1N2, forbiddenab # 所有2位小写字母串共26^2676个。包含ab的串有以ab开头的26个以a结尾且第二位是b的26个但ab本身重复计算了一次。所以包含ab的有2626-151个。 # 那么不包含ab的就有676-51625个。 print(design_password_count(2, ab)) # 应输出 625 # 例2N3, forbiddenaa # 总数为26^317576。 # 包含aa的串计算较复杂可以用我们的函数验证。 print(design_password_count(3, aa)) # 可以手动计算或信任程序 # 例3N1, forbiddenz # 长度为1的密码有26个包含z的只有z本身。所以合法密码有25个。 print(design_password_count(1, z)) # 应输出 25 # 例4N10, forbiddenleetcode # 这是一个较长的禁止串手动计算不可能用于测试程序效率。 print(design_password_count(10, leetcode))调试技巧对于复杂的动态规划如果结果不对可以尝试打印出auto转移表或者在小规模N如1,2,3时打印出每一轮迭代后的dp数组与手工推导的结果进行比对。这是定位逻辑错误最有效的方法。4. 从算法到应用思维模型的延伸解出这道题本身很有成就感但它的价值远不止于此。这种“在构造序列时避免出现某个模式”的模型在软件开发中有着广泛的应用场景。4.1 场景一输入验证与过滤假设你在设计一个论坛系统的用户昵称注册规则。要求昵称不能包含某个敏感词汇T。如果只是简单地在注册时检查昵称是否包含T那么用户可能会使用“T的变体”来绕过比如在中间插入空格、特殊符号如s e n s i t i v e。一个更鲁棒的方法是在客户端或服务端进行实时校验当用户输入每个字符时判断当前已输入的内容是否“接近”敏感词。这本质上就是一个在线状态机匹配问题。我们的auto状态机可以很好地集成到输入框的onChange事件处理中一旦状态达到M匹配完成就立即提示用户输入了违规内容。实操心得在实际应用中敏感词库可能很大。我们可以为每个敏感词单独构建一个状态机然后并行运行如Aho-Corasick自动机正是多模式匹配的扩展。或者将所有敏感词构建成一棵Trie树其失败指针fail pointer的构建思想与KMP的next数组如出一辙。4.2 场景二生成安全的随机标识符有时我们需要生成一批唯一的、随机的标识符如订单号、优惠券码但希望这些标识符中绝对不出现某些令人误解或不当的字符组合例如不希望出现“IL1”、“O0”这样易混淆的序列或者公司禁止的内部代码。我们可以利用类似的DP思想进行“受约束的随机生成”定义状态当前已生成序列的后缀与所有禁止模式的匹配情况。随机选择下一个字符时只从那些不会导致状态转移到“非法状态”即完整匹配任一禁止模式的字符集合中挑选。这样可以保证生成的任何标识符都是“干净”的。这种方法比“先生成后过滤”要高效得多尤其当禁止模式较多或标识符长度较长时可以避免大量无效的生成和比对。4.3 场景三编译原理与词法分析在编写编译器或解释器的词法分析器Lexer时需要将源代码字符串切分成一个个记号Token如标识符、关键字、数字、运算符等。识别每个记号的过程就是一个模式匹配的过程。正则表达式引擎在底层实现时常常会将正则表达式转换为一个非确定有限状态自动机NFA再确定化为DFA。对于关键字这种固定的字符串模式其匹配过程完全可以看作是我们这里讨论的“单模式匹配状态机”。理解KMP和这种DP状态机有助于理解更复杂的自动机原理。5. 常见问题与优化策略实录在实际编码和面试中围绕这个问题会遇到一些典型问题。这里我总结一下。5.1 问题一如何输出具体的密码而不仅仅是计数原题通常只要求计数因为方案数可能天文数字。但如果面试官追问或者题目变体要求如何输出所有方案这时深度优先搜索DFS结合状态机是更合适的方法。我们用DFS递归地构建密码同时维护当前状态state。在每一层我们遍历所有不会导致state转移到M的字符c然后以新状态auto[state][c]进入下一层递归。当密码长度达到N时就将当前路径加入结果列表。注意事项此方法仅适用于N非常小的情况比如N10因为方案数是指数增长的。一定要和面试官确认需求或者只要求输出前K个方案。5.2 问题二如果密码字符集很大比如包含大小写和数字怎么办我们的代码中字符集大小26是一个常数。如果字符集扩大到62a-z, A-Z, 0-9甚至更大算法复杂度依然是 O(N * M * C)其中C是字符集大小。预处理auto表的时间复杂度变为 O(M * C)。只要C不是特别大比如上万算法仍然是可行的。只需要修改代码中字符循环的范围和字符到索引的映射关系即可。优化策略如果字符集极大例如Unicode所有字符预处理的auto表将变得稀疏且巨大内存可能无法承受。此时有两种思路使用字典存储转移将auto从二维数组改为字典数组。auto[state]是一个字典只存储实际可能发生的转移即那些在模式串T中出现的字符或者通过失败指针转移后能匹配的字符。对于其他字符其转移目标通常是0或某个通过失败指针回退到的状态。这可以节省大量空间。在转移时实时计算放弃预处理auto表在DP转移的每一步当需要计算next_state时都实时运行一次KMP匹配过程。这样空间复杂度降到最低但每次转移的时间成本从O(1)升到O(M)因为可能回退。总复杂度变为 O(N * M^2)在M不大时也可接受。5.3 问题三如何处理多个禁止串这是更现实的场景。LeetCode上也有类似题目如“包含所有单词的最小子串”的某种变体。此时单模式的状态机就不够用了。需要升级到多模式匹配自动机即著名的Aho-Corasick (AC) 自动机。AC自动机可以看作是KMP算法在多模式上的扩展。它首先将所有禁止串构建成一棵Trie树然后为每个节点构建失败指针fail pointer其含义与KMP的next数组类似当当前字符匹配失败时跳转到失败指针所指的节点继续尝试。这样我们在构造密码时状态就是AC自动机上的节点。动态规划的定义变为dp[i][node]构造了长度为i的密码当前走到AC自动机的node节点。 转移时对于每个字符c我们从node节点出发沿着自动机的边或失败指针走到下一个节点next_node。如果next_node及其所有通过失败指针链能到达的节点中任何一个是某个禁止串的终点即被打上“终止标记”那么这条转移路径就是非法的。核心区别状态从一维的匹配长度j变成了Trie树节点。非法状态不再是某个固定的M而是任何带有“终止标记”的节点表示匹配了至少一个禁止串。AC自动机的构建和DP转移比单模式复杂但核心思想一脉相承。5.4 问题四大数取模的细节题目通常要求结果对10^97取模。这里有几个坑加法后立即取模如代码所示new_dp[next_state] (new_dp[next_state] current_count) % MOD。避免中间和溢出。使用滚动数组时的初始化每一轮开始new_dp必须初始化为全零。最终求和取模result sum(dp) % MOD。虽然dp中每个元素都已经取过模但它们的和可能仍然超过MOD所以最终求和后需要再次取模。一个更隐蔽的坑是如果题目要求计算的是“方案数对MOD取模的结果”那么在整个计算过程中包括预处理都不应进行任何可能破坏同余性质的操作如除法。我们的算法只涉及加法和乘法常数26可以看作加法所以是安全的。6. 举一反三相关题目与练习建议掌握“设计密码”这道题后你可以尝试解决一系列相关的、难度递进的题目来巩固和深化理解LeetCode 1397. 找到所有好字符串这是“设计密码”的升级版。密码需要满足1) 长度固定为n2) 由特定字符集组成3) 不包含任何“邪恶”子串多个禁止串4) 字典序位于两个给定字符串之间。这需要结合AC自动机处理多模式禁止、数位DP处理上下界约束和动态规划。是道Hard题但思路是相通的。LeetCode 467. 环绕字符串中唯一的子字符串这道题关注的是字符串本身的性质但其中“状态”的定义和转移的思想也有异曲同工之妙。它要求我们找到字符串p在无限环绕字符串...zabcde...xyzabcde...中作为子串出现的唯一字符串数量。解题时我们同样需要记录以某个字符结尾的、满足环绕条件的最长子串长度这可以看作是一种状态。HDU 2457 DNA repair一道经典的AC自动机DP问题。给定一个DNA字符串由AGCT组成其中包含一些“致病模式串”禁止串。问最少需要修改原字符串中的多少个字符每个字符可以改成AGCT中的任意一个才能使其不包含任何致病模式串。dp[i][node]可以定义为处理到原串第i个字符、走到AC自动机node节点时的最小修改次数。POJ 1625 Censored!同样是AC自动机DP要求计算长度为N的、由给定字母表组成的、不包含任何禁止单词的字符串总数。几乎是“设计密码”的多模式版本。练习建议建议的刷题顺序是先彻底理解并能手撕KMP算法LeetCode 28然后搞定设计密码LeetCode 1052思路题接着学习AC自动机模板最后挑战HDU 2457或LeetCode 1397。每做一道题都要问自己状态是什么如何转移边界条件是什么如何优化空间只有通过反复练习和思考这种基于状态机的动态规划模型才能内化成你自己的解题武器。这道题的精髓不在于记忆模板而在于理解“将字符串匹配过程抽象为状态转移”这一核心思想。当你再遇到需要处理“序列约束”、“模式避免”的问题时不妨想想能不能设计一个状态机状态如何定义转移如何发生想明白了这些问题就解决了一大半。