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

后綴樹的概況是什么？

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

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

后綴樹就是一種壓縮后的Trie樹。