后綴樹(shù)的概況是什么？后綴樹(shù)(Suffix tree)是一種數(shù)據(jù)結(jié)構(gòu)，能快速解決很多關(guān)于字符串的問(wèn)題。后綴樹(shù)提出的目的是用來(lái)支持有效的字符串匹配和查詢(xún)。學(xué)習(xí)后綴樹(shù)之前，先了解一下Trie這個(gè)數(shù)據(jù)結(jié)構(gòu)Tr

后綴樹(shù)的概況是什么？

后綴樹(shù)(Suffix tree)是一種數(shù)據(jù)結(jié)構(gòu)，能快速解決很多關(guān)于字符串的問(wèn)題。后綴樹(shù)提出的目的是用來(lái)支持有效的字符串匹配和查詢(xún)。

學(xué)習(xí)后綴樹(shù)之前，先了解一下Trie這個(gè)數(shù)據(jù)結(jié)構(gòu)Trie是一種搜索樹(shù)，可用于存儲(chǔ)并查找字符串。Trie每一條邊都對(duì)應(yīng)一個(gè)字符。在Trie中查找字符串S時(shí)，只要按順序枚舉S的各個(gè)字符，從Trie的根節(jié)點(diǎn)開(kāi)始選擇相應(yīng)的邊走，如果枚舉完的同時(shí)恰好走到Trie樹(shù)的葉子節(jié)點(diǎn)，說(shuō)明S存在于Trie中。如果未到達(dá)葉子節(jié)點(diǎn)，或者枚舉中未發(fā)現(xiàn)相應(yīng)的邊，則S沒(méi)有被包含在Trie中。

后綴樹(shù)就是一種壓縮后的Trie樹(shù)。