Ama*_*hal 9 string algorithm suffix-array
我们需要在两个字符串之间找到最短的不常见子字符串,即如果我们有两个字符串a,b那么我们需要找到其中最短子字符串的长度a不是子字符串b.
如何使用后缀数组解决这个问题？
要求解决的复杂度不超过n*lg(n)
Evg*_*uev 11
这可以使用广义后缀树在O(N)时间内求解.
在O(N)时间内构造广义后缀树之后,需要执行广度优先搜索并找到不属于这两个字符串的第一个节点.从根到此节点的路径提供了最短的不常见子字符串.
对于两个输入字符串,也可以在O(N)时间内使用广义后缀数组来完成相同的操作.
构造通用后缀数组以及LCP数组(或稍后从后缀数组构造LCP数组).添加单个零元素作为LCP数组的前缀; 添加另一个零元素作为后缀.找到一对最小LCP条目,使得只有一个字符串的后缀由这些条目分隔.这意味着您需要对LCP阵列执行线性扫描,提取两个最小值,但每次看到不同字符串的后缀或者如果您看到属于两个字符串的后缀时,都将最小值重置为无穷大.这些对中最好的元素中较大的元素(对中较大元素的值最小)给出了最短的不常见子串的长度.这工作,因为这对极小值界定的第一个节点的所有后代(最靠近根),不属于在相应的后缀树两个字符串.