如何在伪多项式时间内从文本串表中找到字符串的最优编码？

你之前的O(n²mk)思路的冗余点在于枚举了所有可能的子串长度，实际上因为码表中每个字符串长度都不超过k，我们只需要检查每个位置前最多k位的匹配情况即可，配合动态规划就能达到要求的时间复杂度。

1. 动态规划状态定义 #

定义 dp[i] 为编码数据串D的前i个字符所需的最少码字数量：

• 初始状态：dp[0] = 0（空串不需要编码），其余dp[1..n]初始化为无穷大。
• 最终结果：dp[n]就是整个串的最优编码长度。

2. 状态转移规则 #

从左到右依次计算每个dp[i]（i从1到n），对每个i遍历码表中的全部m个字符串：

• 设当前码表字符串为s，长度为l（1 ≤ l ≤k）
• 先判断i ≥ l：只有前i个字符长度不小于s的长度，才可能以s作为最后一个码字
• 再逐字符比对D的末尾l个字符D[i-l:i]是否和s完全相等
• 若两者都满足，更新状态：dp[i] = min(dp[i], dp[i-l] + 1)

3. 复杂度验证 #

• 总共有n个dp状态需要计算
• 每个状态需要遍历m个码表字符串
• 每个字符串的逐字符比对最长耗时为k
• 总时间复杂度为O(nmk)，完全符合题目要求。

实例匹配验证 #

用题目给出的示例验证：
码表为(a,ba,abab,b)，数据串bababbaababa长度为12。
计算dp[1]时，匹配到码表的b，得到dp[1] = dp[0]+1 =1；
计算dp[5]时，匹配到码表的abab（长度4），检查D[1:5] = abab完全匹配，得到dp[5] = dp[1]+1 =2，对应最优编码的前两个码字b,abab，和题目给出的最优方案完全一致。

内容的提问来源于stack exchange，提问作者prakash sellathurai