如果字符串 S 的长度为 n ,则可以使用LCP数组在线性时间内查找不同子字符串的计数 . 而不是要求整个字符串 S 中的唯一子字符串计数,查询 q 包含索引 (i,j) ,其中 0 <= i <= j < n 要求在字符串 S[i..j] 的给定查询范围内计算不同的子字符串 .

我的方法是将LCP数组的线性时间构造应用于每个查询 . 它给出了复杂性 O(|q|n) . 查询数量可能会增加到 n 的顺序,因此回答所有查询会使其成为 O(n^2) .

每个查询的线性时间可以做得更好吗?

通常,如果我们已经有后缀数组,后缀树,lcp数组的字符串的一个进程子字符串,那些结构不再相关,并且必须再次从头开始构建?