最短的不寻常子字符串:一个字符串的最短子字符串，即不是另一个字符串的子字符串。
最短的不寻常子字符串:一个字符串的最短子字符串，即不是另一个字符串的子字符串。
提问于 2012-09-26 17:49:44
我们需要在两个字符串之间找到最短的不寻常子串，也就是说，如果我们有两个字符串，a和b，那么我们需要找到a的最短子字符串的长度，它不是b的子字符串。
如何使用后缀数组来解决这个问题？
求解的复杂度不超过n*lg(n)
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-09-26 18:00:49
这可以用广义后缀树在O(N)时间内解决。
在O(N)时间构造了广义后缀树之后，您需要执行广度优先搜索，并找到不属于这两个字符串的第一个节点。从根到此节点的路径提供最短的不寻常子字符串。
对于两个输入字符串，也可以在O(N)时间内使用广义后缀数组进行同样的操作。
与LCP阵列一起构造广义后缀数组(或稍后从后缀数组构造LCP数组)。添加单个零元素作为LCP数组的前缀；添加另一个零元素作为后缀。找到一对最小的LCP条目，以便只有一个字符串的后缀由这些条目分隔。这意味着您需要对LCP数组执行线性扫描，提取两个最小值，但每次看到不同字符串的后缀或如果您看到属于这两个字符串的后缀时，则将这两个最小值重置为无穷大。这些对中最好的元素中最大的元素(对中较大的元素的值最小)给出了最短的不寻常子字符串的长度。这是因为这一对极小值分隔了第一个节点的所有子节点(最接近根)，而不是属于相应后缀树中的两个字符串。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12607512
复制相关文章
相似问题
腾讯云开发者
