de Bruijn 序列 B(k, n) 的定义是 { 0, 1, ..., k-1 } 的有限序列 X = X[1]X[2] ... X[L] 使 L >= n 且所有 { 0, 1, ..., k-1 }^n 的元素都在 X' = X[1] X[2] ... X[L] X[1] X[2] ... X[n-1] 恰好作为子串出现一次。已经知道 B(k, n) 的长度是 L = k^n ，注意 X ' 长度为 n 的子串恰好有 L = k^n 个，且 { 0, 1, ..., k-1 }^n 恰好就有 k^n 个元素。
在你的情况里 k=10, n=6 ，但 de Bruijn 序列并不是你直接要的答案，不过已经非常接近了。
你希望寻找一系列长度是 12 的串 Y(1), ..., Y(z) 使得诸 Y(i) 的所有长度为 6 的子串覆盖了 { 0, ..., 9 }^6 ，很明显 z >= ceiling(10^6/7) = 142858 ，而取
Y(i) = X'[7(i-1)+1] ... X[7(i-1)+12]
1 <= i <= 142857
Y(142858) = X'[7(142858-1)+1 = 10^6] ... X'[10^6+(10-1)] 0 0
则诸 Y(i) 的所有长度为 6 的子串当然就包括了 X' 所有长度为 6 的子串，后者就是所有长度为 6 的串。这说明需要的 z 可以是 142858 。
暂且称上面长度为 12 的串是“窗口”。类似地，可以算出密码字符有 k 个，密码长度是 n ，窗口长度是 m 的时候需要的最小的窗口数就是 ceiling(k^n/m)。
计算最小窗口数和计算这一系列窗口是两回事儿，不过后者也不难，de Bruijn 序列有算法可以生成，再练习一下使用搜索引擎的能力就好。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。