字符串後綴樹的隱式表示

Question

從數據結構與算法分析Java中，魏斯匹配：

維斯寫道：

1. 在樹葉中，我們使用後綴開始的索引（如在後綴數組中）
2. 在內部節點中，我們存儲從根開始匹配的常用字符數，直到內部節點;這個數字代表字母深度。

我的問題：給定的輸入字符串（例如「香蕉」）和後綴樹的隱式表示，將好的算法用於字符串搜索是什麼樣子？我見過的算法假定樹的不同表示。我想做子串搜索而不轉換成不同的樹形表示。

Answer 1

我從來沒有見過這種表現形式。將邊上的標籤表示爲從原始字符串中勾勒出一系列字符的整數對更爲常見，這可以讓您更輕鬆地確定邊緣上的字符（您可以回頭看看原始字符串字符在需要的基礎上，以查看它們是否與您正在查看的子字符串匹配）。

我相當肯定，這種壓縮表示不匹配子字符串。爲了追隨邊緣，你需要知道邊緣上的字符是什麼，但是除非你掃描原始字符串的字符以找到可能匹配的東西，否則你不能分辨這些字符是什麼。您可以考慮降序到子樹中以找到後綴並使用它來重構字符，但這需要額外的時間並打破您期望後綴樹的時間範圍。

我最好在這裏猜測，作者誤解了如何在少量空間中表示後綴樹。