Thực đơn
Cây_hậu_tố Chức năngCó thể xây dựng cây hậu tố cho xâu S {\displaystyle S} độ dài n {\displaystyle n} trong thời gian Θ ( n ) {\displaystyle \Theta (n)} , nếu bảng chữ cái có kích thước đa thức (và do đó cũng đúng khi bảng chữ cái có kích thước hằng số).[5]Với bảng chữ cái lớn hơn, đa số thời gian chạy là cho việc sắp xếp các chữ cái để đưa chúng về kích thước O ( n ) {\displaystyle O(n)} ; trong trường hợp tổng quát, việc này tốn thời gian O ( n log n ) {\displaystyle O(n\log n)} .Các kết quả dưới đây là cho trường hợp kích thước bảng chữ cái là hằng số.
Giả sử đã có cây hậu tố cho xâu S {\displaystyle S} độ dài n {\displaystyle n} , hoặc đã có cây hậu tố tổng quát cho tập hợp các xâu D = { S 1 , S 2 , … , S K } {\displaystyle D=\{S_{1},S_{2},\dots ,S_{K}\}} với tổng độ dài n = | n 1 | + | n 2 | + ⋯ + | n K | {\displaystyle n=|n_{1}|+|n_{2}|+\cdots +|n_{K}|} . Ta có thể:
Có thể xây dựng một cấu trúc dữ liệu hỗ trợ cho cây hậu tố trong thời gian Θ ( n ) {\displaystyle \Theta (n)} để tìm tổ tiên chung thấp nhất của các nút trong thời gian hằng số([6] chương 8). Khi đó có thể:
Thực đơn
Cây_hậu_tố Chức năngLiên quan
Cây hậu tốTài liệu tham khảo
WikiPedia: Cây_hậu_tố http://webhome.cs.uvic.ca/~mgbarsky/DIGEST_SEARCH http://code.google.com/p/patl/ http://www.zbh.uni-hamburg.de/staff/kurtz/papers/G... http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_t... http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf http://www.cs.ucdavis.edu/~gusfield/strmat.html http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/su... http://www.cs.helsinki.fi/group/suds/ http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFi... http://www.nist.gov/dads/HTML/suffixtree.html