文摘
A kk-ary de Bruijn sequence of order nn is a cyclic sequence of length knkn in which each kk-ary string of length nn appears exactly once as a substring. A shift rule for a de Bruijn sequence of order nn is a function that maps each length nn substring to the next length nn substring in the sequence. We present the first known shift rule for kk-ary de Bruijn sequences that runs in O(1)O(1)-amortized time per symbol using O(n)O(n) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131).