后綴樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)，它支持有效的字符串匹配和查詢。 一個(gè)具有m個(gè)詞的字符串S的后綴樹(shù)T，就是一個(gè)包含一個(gè)根節(jié)點(diǎn)的有向樹(shù)，該樹(shù)恰好帶有m個(gè)葉子，這些葉子被賦予從1到m的標(biāo)號(hào)。 每一個(gè)內(nèi)部節(jié)點(diǎn)，除了根節(jié)點(diǎn)以外，都至少有兩個(gè)子節(jié)點(diǎn)，而且每條邊都用S的一個(gè)非空子串來(lái)標(biāo)識(shí)。出自同一節(jié)點(diǎn)的任意兩條邊的標(biāo)識(shí)不會(huì)以相同的詞開(kāi)始。后綴 樹(shù)的關(guān)鍵特征是：對(duì)于任何葉子i，從根節(jié)點(diǎn)到該葉子所經(jīng)歷的邊的所有標(biāo)識(shí)串聯(lián)起來(lái)后恰好拼出S的從i位置開(kāi)始的后綴，即Si,…,m。樹(shù)中節(jié)點(diǎn)的標(biāo)識(shí) 被定義為從根到該節(jié)點(diǎn)的所有邊的標(biāo)識(shí)的串聯(lián)。