後綴樹（二進制字符串）：查找最長的子字符串

Question

尋找一種有效的算法來查找字符串中具有其互補字符串的最長子字符串（按位）。

這就是我說的話互補串按位：

100011 
011100 

Answer 1

這是一個簡單的O（n）算法，依靠後綴樹構造。

將原始字符串s和補碼串s'加載到相同的後綴樹（O（n）time）中。然後通過爲每個節點x設置兩個標誌f（x）和f'（x），在f（x）（或f'（x））包含s（後綴） S'）。現在簡單地遍歷樹，尋找具有兩個標誌設置的最深節點，並且發現s中最長的字符串，其補碼也出現在s中。後處理也僅花費O（n）時間，因此總運行時間爲O（n）。

Answer 2

下面的算法是最壞的情況下O(n * n)和平均情況只是有點超線性。當有很多很長的常見子字符串時，它遇到了最壞的情況。

考慮可以通過在字符串中的任意位置開始形成的子字符串集。一旦只有一個可能的匹配，就構建這些子字符串的一個trie，該字符串以指向原始字符串中某個位置的指針結尾。你必須爲n個子字符串中的每一個工作這個trie，但是你只需要通過該字符串與其他任何其他字符串中最長的公共子字符串來跟蹤它。

一旦你建立了這個數據結構，通過查找樹的遞歸遍歷，尋找一個子串與它的補碼進行配對。由於你只需要配對相反的子字符串，而不是子字符串與字符串中其他所有的位置，因此trie的結構應該使配對非常有效。

如果某些字符在共同點不常見時很常見，那麼您可以通過延遲建立trie來提高性能。