后綴樹最長公共子串

後綴樹（Suffix Tree）是一種數據結構，用於存儲字元串的所有後綴，以便快速查找字元串的子串。最長公共子串（Longest Common Substring, LCS）問題是指給定兩個或多個字元串，找到它們共有的最長的子串。

在後綴樹的基礎上，我們可以通過以下步驟來找到兩個字元串的最長公共子串：

1. 構建後綴樹：首先，我們需要為給定的兩個字元串分別構建後綴樹。

2. 找到公共節點：遍歷兩個後綴樹，找到它們共有的節點。這些節點表示的是兩個字元串中都存在的子串。

3. 遞歸查找：從公共節點出發，遞歸地檢查其子節點，看它們是否也是公共節點。如果某個子節點是公共節點，那麼它代表的子串就是最長公共子串的一部分。

4. 更新最長子串：每次找到一個公共子串後，更新最長公共子串的長度。

5. 回溯：通過回溯找到最長公共子串的起始位置和結束位置。

下面是一個簡單的例子：

給定兩個字元串 "ABCDAB" 和 "ABCDABCDAB"，它們的最長公共子串是 "ABCDAB"。

構建後綴樹後，我們可以看到這兩個字元串的後綴樹有很多公共節點，通過遞歸查找和更新最長子串，我們可以找到這個最長公共子串。

需要注意的是，後綴樹並不是專門為了解決最長公共子串問題而設計的，它的時間複雜度是 O(n)，空間複雜度是 O(n)，其中 n 是字元串的長度。對於尋找最長公共子串問題，有更高效的算法，比如動態規劃算法，其時間複雜度是 O(mn)，其中 m 和 n 分別是兩個字元串的長度。在實際套用中，通常會根據具體情況選擇合適的算法。