string - Shortest uncommon substring：一个字符串的最短子字符串，即不是另一个字符串的子字符串

Question

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

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

以不超过 n*lg(n) 的复杂度求解

Answer 1

这可以用广义后缀树在 O(N) 时间内解决。

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

---

同样的事情也可以在 O(N) 时间内使用两个输入字符串的通用后缀数组来完成。

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