断头指标254教学教案.ppt

文档介绍：ß.LinearBidirectionalOn-,20032OutlineIntroductiontoAffixTreeOnlineconstructionofSuffixTreeinreversedorderOnlineconstructionofAffixTreeOnlinebidirectionalconstructionofAffixTree3Path(n)路徑(n)w=path(n):npath(n)=bbabacbbabac5CST&CPT(pactSuffixTree(CST):字串(T)={u|uisasuffixoft}Example:S=pactSuffixTree(CST)abaababbbbbb6CST&CPT(pactPrefixTree(CPT):字串(T)={u|uisaprefixoft}Example:S=pactPrefixTree(CPT)bbaaaaaabbbb7AffixTree(1)Prefixesoftaresuffixesof反(t)PrefixTree(t)=SuffixTree(反(t))Example:T=baabb 反(T)=pactPrefixTree(CPT)ofT8AffixTree(2)斷頭指標SuffixLinksExample:T=abcTheCSTfort=ababc9AffixTree(2)斷頭指標上的labelThesubstringthatisdiscardedExample:t=abcTheCSTfort=ababcabababc10