Ukkonen算法是一種用於構建後綴樹的線上算法，它能夠在不知道整個輸入字元串的情況下，通過逐步添加字元來構建後綴樹。該算法的主要思想是在添加新字元時，使用字元串上的一段區間來表示樹中的一條邊，並根據需要自動擴展或分裂邊。Ukkonen算法的優點在於其代碼簡潔且執行效率高，其時間複雜度為O(n)，使得它成為構建後綴樹的優選算法之一。
算法的核心在於維護一個當前節點（now）和剩餘未處理的後綴長度（remain）。在處理每個新字元時，算法首先確定當前應插入的後綴長度，然後根據當前節點的出邊情況採取不同的操作：
如果不存在需要的出邊，直接添加新邊。
如果存在匹配的出邊，即後綴隱含在現有邊中，則不進行操作。
如果存在出邊但字元不匹配，需要分裂這條邊。
Ukkonen算法利用了一個重要的觀察結果：對於後綴構建的後綴樹，下一個要插入的後綴是當前後綴的下一個後綴。這一性質允許算法在添加新後綴時，能夠快速跳轉到正確的位置，進一步最佳化了算法的效率。
為了從隱式後綴樹轉換到顯式後綴樹，Ukkonen算法使用一個特殊字元來明確所有隱含的路徑，從而完成後綴樹的構建。
總結來說，Ukkonen算法是一個高效、線上的後綴樹構建算法，它通過在添加新字元時自動擴展和分裂邊，實現了在不知道整個輸入字元串的情況下構建後綴樹的目標。其時間複雜度為O(n)，適用於處理大規模文本數據。