de Bruijn序列查寻表标签的末位基准构造法

摘要

de Bruijn序列结构是一个查寻表,其核心是它的表标签.因此构造出查寻表标签对于生成de Bruijn序列十分重要.本文给出一种m+1元n级de Bruijn序列查询表标签的末位基准构造法.方法一为末住复制构造法,即对大部分节点用构成该节点的串的末位字符拷贝值作为该节点的标签.方法二为末位分组构造法,即对大部分节点按构成该节点的串的末位字符值分成两组,第一组的标签设为定值,第二组的标签任取为第一组节点的末位值.这些方法构造的壹寻表标签数随着m,n增长而成指数式增长.但仍与定值构造法一样,在局部看是有效的,但与查寻表标签本身数目的惊人增长比较起来就很渺小.方法二与定值标签构造法比较其速度提高了关于m和n的指数式倍.