最短的非公共子串：一个字符串中最短的子串，该子串不是另一个字符串的子串。

Question

我们需要找到两个字符串之间最短的非公共子串，即如果我们有两个字符串a和b，那么我们需要找到a的最短子串长度，该子串不是b的子串。

如何使用后缀数组解决这个问题？

要求解的复杂度不超过n*log(n)。

- Aman Singhal

---

可能在计算机科学上相同（更新）：http://cs.stackexchange.com/questions/12037/shortest-sub-sequence-of-one-string-thats-not-a-sub-sequence-of-another-string - Ciro Santilli OurBigBook.com

Answer 1

可以使用广义后缀树以 O(N) 的时间解决这个问题。

在 O(N) 的时间内构建广义后缀树后，需要执行广度优先搜索并找到第一个不属于两个字符串的节点。从根到该节点的路径给出了最短的非公共子串。

---

同样地，可以使用两个输入字符串的广义后缀数组在 O(N) 的时间内完成相同的操作。

构造广义后缀数组和 LCP 数组（或稍后从后缀数组构造 LCP 数组）。将单个零元素添加为 LCP 数组的前缀；再添加另一个零元素作为后缀。以这种方式找到一对最小的 LCP 条目，使得只有一个字符串的后缀由这些条目分隔。这意味着您需要线性扫描 LCP 数组，提取两个最小值，但每次看到不同字符串的后缀或者看到属于两个字符串的后缀时都必须将两个最小值重置为无穷大。这些对中最佳对中较大的元素（具有对中较大元素的最小值）给出了最短的非公共子串的长度。这起作用是因为这对最小值限定了不属于相应后缀树中两个字符串的第一个节点（最靠近根的节点）所有后代。

- Evgeny Kluev

---

为什么要用零填充LCP？如果我们始终扫描LCP以寻找两个最小值，那还是O（n）吗？对于我所有的问题都很抱歉，您能否也提供一个示例？ - Chris Zhang

@ChrisZhang：在填充零时并不是严格必要的。它只是允许避免处理数组开头/结尾的特殊情况。是的，它仍然是O(n)；将其与在数组中找到2个最小值的情况进行比较，将每个数组元素插入到常数大小为2的最大堆中。很抱歉没有想出足够简单的例子。也许这篇论文能帮到你："用增强后缀数组替代后缀树"。它解释了如何将几乎任何后缀树算法转换为SA算法。回答这个问题时我还不知道这个。 - Evgeny Kluev

使用广义后缀树的解决方案是不正确的，因为在后缀树中边的长度可以是任意的（使用后缀trie可能会起作用）。在广度优先搜索中找到一个非共享节点时（实际上深度优先搜索应该同样有效），候选解决方案是到最后一个共享节点的路径加上新发现的边的第一个字符。这个长度可以与之前最短的结果进行比较，并且如果它是更短的解决方案，则替换它。（如果当前最短的子字符串长度为1，则可以停止搜索。） - uli_1973

@uli_1973：实际上这里需要的是到任何非共享节点的单源最短路径。这绝对可以通过检查每个树节点并选择距离根最短的节点来完成。但更自然的算法是使用BFS，并在找到非共享节点时立即停止。当然，这个BFS应该被推广到后缀树上：普通队列应该被优先队列替换。（可能更好的命名方式不是“推广BFS”，而是“简化Dijkstra算法”）。 - Evgeny Kluev