前綴樹和字典樹 后綴樹的概況是什么?
后綴樹的概況是什么?后綴樹(Suffix tree)是一種數(shù)據(jù)結(jié)構(gòu),能快速解決很多關(guān)于字符串的問(wèn)題。后綴樹提出的目的是用來(lái)支持有效的字符串匹配和查詢。學(xué)習(xí)后綴樹之前,先了解一下Trie這個(gè)數(shù)據(jù)結(jié)構(gòu)Tr
后綴樹的概況是什么?
后綴樹(Suffix tree)是一種數(shù)據(jù)結(jié)構(gòu),能快速解決很多關(guān)于字符串的問(wèn)題。后綴樹提出的目的是用來(lái)支持有效的字符串匹配和查詢。
學(xué)習(xí)后綴樹之前,先了解一下Trie這個(gè)數(shù)據(jù)結(jié)構(gòu)Trie是一種搜索樹,可用于存儲(chǔ)并查找字符串。Trie每一條邊都對(duì)應(yīng)一個(gè)字符。在Trie中查找字符串S時(shí),只要按順序枚舉S的各個(gè)字符,從Trie的根節(jié)點(diǎn)開始選擇相應(yīng)的邊走,如果枚舉完的同時(shí)恰好走到Trie樹的葉子節(jié)點(diǎn),說(shuō)明S存在于Trie中。如果未到達(dá)葉子節(jié)點(diǎn),或者枚舉中未發(fā)現(xiàn)相應(yīng)的邊,則S沒(méi)有被包含在Trie中。
后綴樹就是一種壓縮后的Trie樹。