从指数级到高效：Knuth Algorithm C 构建 Commafree Code
引言
如果你可以创建一组无需逗号或分隔符就能唯一解码的代码，这会对 DNA 测序、数据压缩和错误校正产生什么影响？
这不是纯粹的学术好奇——commafree codes 在这些领域都有实际应用。在我上一篇文章中，我们探讨了指数级复杂度的递归算法。今天，我们将深入 Knuth 的 Algorithm C，它通过巧妙的回溯和稀疏数据结构实现了惊人的效率。
本文你将学到：
- Algorithm C 如何将复杂度从 O(2^n) 降低到可管理的水平
- 用于剪枝搜索空间的 ingenious “poison array” 技术
- 实用的实现技巧和性能优化方法
无论你是正在研读 TAOCP 4B，还是单纯热爱优雅算法，这篇深度解析都将改变你对组合搜索的思考方式。
再战commafree code——暴力挑选&优化
引言
在上一篇文章中，我们生成了参数 m=3、n=4 时的所有可能 commafree code。本文将介绍如何从这18个码中挑选出一个最大的子集，使其满足 commafree code 的性质：当集合中任意两个码相连接时，不考虑首尾各n个字母后，中间所有长度为n的子串都不在这个集合中。
由于一个码可以和自身连接，比如选择0001后，序列00010001中的所有长度为4的中间子串(0010、0100、1000)都不能出现在最终集合中。这意味着如果我们选择了某个码，它的所有循环移位都不能再加入集合。因此，对每个主码，我们只需要从它的4个循环移位中选择一个加入集合。
