问最短的不寻常子字符串:一个字符串的最短子字符串，即不是另一个字符串的子字符串。

EN

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

在O(N)时间构造了广义后缀树之后，您需要执行广度优先搜索，并找到不属于这两个字符串的第一个节点。从根到此节点的路径提供最短的不寻常子字符串。

对于两个输入字符串，也可以在O(N)时间内使用广义后缀数组进行同样的操作。

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