如何查找n個字符串的不同子字符串的數量？

Question

給定n個字符串，每個length <=10^5。

輸入：「aa ab ac ad」

輸出：8(「a」,」b」,」c」,」d」,」aa」,」ab」,」ac」,」ad」)

輸入：「aab bcd」

輸出：10(「a」,」b」,」c」,」d」,」aa」,」ab」,」bc」,」cd」,」aab」,」bcd」)

更新：

スffix樹是一個解決方案，但它需要更多的內存。

除了後綴樹還有解決方案嗎？

我試過，但我沒有找到任何算法，以有效的方式解決這個問題。

Answer 1

後綴樹。除了設置後綴樹之外，您不需要執行任何操作，它恰好是一個列出任何字符串或字符串集合的所有不同子字符串的結構。