“好串”求解算法优化原理与Python实现

题目要求：称一个 0-1 串是“好串”，如果它的任何子串不在其中连续出现三次以上。编写程序，输入正整数 n，输出某个长度为 n 的好串。

在数学学上可以证明：存在任意长度的好串。事实上，若 w 是一个长度为 k 的好串，将 w 中的 0 和 1 分别替换为 01 和 10 必然是一个长度为 2k 的好串（感兴趣的读者可以用反证法证明）；同时，好串的任意子串必然也是好串。

显然，单独的 0 和 1 都是好串，根据上面的性质，可以得到任意长度的好串。根据这个思路（称为“标准迭代”），可以写出下面的代码：

这个程序只有四行，算是十分短小精悍的。但是，它的可读性并不好：同时，还用到了 lambda 表达式、map 函数、字符串与列表的相互转化等十分复杂的机制；更重要的是，它的执行效率不高。

这时，应当仔细分析一下这个问题的特殊性 —— 考虑下面的 01-串序列：0、01、0110、01101001、…… （其规律为：下一个串是在上一个串的基础上添加原串的对偶串（即按位取反的串）获得）。

不难归纳证明：如果用 0 作为起始好串，上面的串列与按照标准方式迭代的序列恰好一样。

按位取反可以通过与一个全 1 序列进行异或操作得到，这样就获得了下面的代码：

细节：倒数第二行之所以需要切片操作，是因为要把异或后字串的符号位去掉。

这样，代码的效率与可读性较之于第一个版本有了大幅度的提高。但是，循环体代码里面仍然存在着进制转换、移位、求长度、切片等操作，效率仍然不是十分令人满意。同时，总感觉该问题某些特殊的性质没利用上！什么性质呢？—— 对！就是“对称性”！！！

想到了这三个字，代码的样子马上就会发生翻天覆地的变化！

这时，你可能不太相信，解决这个问题的代码竟可以简单成这样：循环体中，只存在简单的字串连接操作！

但是，冷静！这是仍然应该问一下自己：还能继续优化吗？ 中国传媒大学胡凤国老师敏锐的指出：这段代码跟原来比，多耗费了一倍的空间！

这的确是一个问题！怎么解决呢？事实上，串的长度每次增加一倍，这个“浪费”只出现在循环的最后一步！如果我们让循环少做一次，不就可以了吗？ 终极代码如下：