后缀树（二进制字符串）：查找最长的子字符串

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来提高性能。