看動畫學算法系列之:字尾樹suffix tree

簡介

字典樹trie

壓縮字典樹

字尾樹suffix tree

字尾樹的搜尋

查找最長重複子字元串

查找兩個字元串的最長公共子字元串

字尾樹的代碼實作

模式比對是一個在工作中經常會用到的場景，比如說給定一個字元串數組txt[0…n-1]和要比對的模式pat[0…m-1]，我們希望找出所有在txt中能夠比對模式字元串的次數。這就叫做模式比對。

要想完成字元串比對的任務，我們其實有兩種方式，第一種方式就是使用各種模式比對的算法，比如kmp，rabin karp，finite automata based和boyer moore。 這些比對算法最好的時間複雜度是o(n)，其中n是字元串的長度 。

還有一種方式是對要查詢的字元串數組進行預處理，處理過後再進行比對的話，時間複雜度可以減少到o(m)，其中m是要比對的模式的長度。

實際上這就是空間換時間的概念，假如我們有一本康熙字典，即使是o(n)的時間複雜度也住夠長了，如果能夠進行預處理之後，o(m)的時間複雜度将會大大減少我們的搜尋時間。

那麼是不是所有的字元串的模式比對都可以使用預處理呢？

當然不是，因為預處理是需要耗費時間的，預處理的情況隻适用于一次