這是什麼數據結構？

Question

我得到了一組（沒有重複然後）的任意長度和數字的二進制字符串，並需要找出是否有任何字符串是其他字符串的前綴。對於小集合和小長度的字符串，這很容易，只需通過讀取每個字符串來構建一個二叉樹，無論何時我找到一個前綴匹配，即時完成，但是由於長度很長的字符串很多，此方法效率不高。只是想知道這是一個什麼樣的正確的數據結構和算法。哈夫曼樹？嘗試（基數樹）？或什麼？謝謝。

Answer 1

我會去與trie。使用trie，插入所有字符串，以便每個字符串的最後一個節點標記一個標誌，然後對於每個字符串，沿其路徑行走，並檢查頁面上的任何節點是否設置了標誌。如果是，那麼結束於該節點的字符串是您正在分析的字符串的前綴。

假設n =字符串數量，k =平均長度，插入和分析兩者總共需要O（kn）。

前綴樹（節點長度超過單個字符的樹）可能效率更高，但不易實現。