algorithm - 后缀树(二进制字符串): Find longest substring

Question

寻找一种有效的算法来找到字符串中最长的子字符串，该子字符串也具有其互补字符串(按位)。

这就是我所说的按位互补字符串的意思:

100011
011100

Answer 1

这是一个简单的 O(n) 算法，它依赖于后缀树构造。

将原串s和补串s'加载到同一个后缀树中(O(n)时间)。然后通过为每个节点 x 设置两个标志 f(x) 和 f'(x) 来对这棵树进行后处理，当 f(x)(resp. f'(x))包含后缀 s(resp。 s')。现在简单地遍历树寻找设置了两个标志的最深节点，并且您找到了 s 中最长的字符串，其补码也出现在 s 中。后处理也仅花费 O(n) 时间，因此总运行时间为 O(n)。