9
$\begingroup$

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ containing indexing $(i,j)$ where $0 \le i \le j < n$ is asking for count of distinct substring inside given query range for string $S[i..j]$.

My approach is just applying linear time construction of LCP array to each query. It gives complexity $O(|q|n)$. Number of queries could raise to order of $n$ so answering all queries makes it $O(n^2)$.

Can it be done better, than linear time for every query?

In general, if one process substring of string for which we already have suffix array, suffix tree, lcp array, are those structures not relevant anymore, and must be build from scratch again?

Improve this question
$\endgroup$
4
  • $\begingroup$ The size of input and output seem to be natural lower bounds. $\endgroup$
    – Raphael ♦
    Jun 14, 2017 at 5:59
  • 1
    $\begingroup$ I don't have time to think about this, but it's quite standard to build segment trees out of these complex structures (in competitive programming), maybe it's the case for suffix arrays/trees/etc. You just have to be clever in defining a fast "combine" operation (which will be used for a father node with his children, or at the end to combine the results of all the leaves covering your interval). $\endgroup$
    – md5
    Jun 14, 2017 at 8:44
  • $\begingroup$ The number of queries is the number of ordered pairs $i, j$ which is $(n*(n+1))/2$, so the complexity should be $O(n^3)$ $\endgroup$
    – user11171
    Jul 3, 2018 at 22:45
  • $\begingroup$ @md5 I don't think a segment tree (or fenwick tree) based solution will work because the number of substrings lacks additive inverse. $\endgroup$
    – user11171
    Jul 4, 2018 at 16:27

2 Answers 2

Reset to default
1
$\begingroup$

There is $O(n \sqrt{n} + |Q| \sqrt{n})$ offline solution.

  1. Sort elements $(i,j)$ of $Q$ in ascending order of $j$.
  2. Distribute them into $\sqrt{n}$ buckets so, that $(i,j)$ goes into bucket number $\lfloor \frac{i}{\sqrt{n}} \rfloor$.
  3. For each bucket starting at $b$ and each query $(i,j)$ in it, build a suffix tree for $S[b,j]$.
  4. For each query in a bucket, remove redundant characters from the left and report the answer.

Step 3 takes $O(n)$ for each bucket, because we use Ukkonen's algorithm and $j$ goes in ascending order.

Step 4 takes $O(\sqrt{n})$ for each query, because removing $\sqrt{n}$ longest suffixes from the tree takes $O(\sqrt{n})$. Note that you can use an indirection layer to avoid modifications to the original suffix tree.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The number of distinct substrings is the number of paths in the suffix tree that start at the root and end at a node with just a single leaf below it, correct? Do you store these path counts explicitly in the notes? If so, then how do you update things when removing the first character in O(1) time? There could be up to $\sqrt n$ of them (in the case where the first character is unique within the block). If not, how do you compute them on the fly? $\endgroup$
    – j_random_hacker
    Jul 8, 2018 at 7:49
  • $\begingroup$ @j_random_hacker Ukkonen's algorithm builds so called implicit suffix tree. Number of distinct substrings is just sum of lengths of its edges (i.e. size of corresponding trie). $\endgroup$
    – Dmitri Urbanowicz
    Jul 8, 2018 at 14:14
0
$\begingroup$

The question does not motivate the number of queries being $O(n)$, which seems an arbitrary worst case since the number of unique possible queries is the number of ordered pairs and thus $O(n^2)$.

Here are two different solutions with better time complexity for the $O(n^2)$ case based on (implicit) suffix trees constructed incrementally with Ukkonen's algorithm. Both solutions are based on preprocessing and have complexity $O(n^2 + |Q|)$ where $Q$ is the set of queries. The second solution runs in $O(n + |Q|)$ if all queries have the same width.

Solution 1 - Preprocess all unique queries

Iterate over the suffixes of $S$. For each suffix $S_i=S[i..n]$, build the suffix tree of $S_i$ with Ukkonen's algorithm. After update $j$ to the current suffix tree, store the tree size in a matrix at position $(i,i+j-1)$. A query for the range $[x,y]$ is answered by the matrix element at $(x,y)$.

Suffix tree size can be stored along with the suffix tree and updated in constant time at each step by modifying the update procedure in Ukkonen's algorithm. For each update the size increases by the current number of leaves.

Solution 2 - Preprocess unique query widths

This solution is harder to implement but requires less preprocessing work if there are few query widths. Preprocessing takes $O(n)$ time if there is only one query width.

For each query width $w$, use a sliding window of width $w$ and incrementally build a suffix tree. Remove the suffix starting one character to the left of the window by remove the longest suffix from the tree. At each step, the current number of substrings within the sliding window is the tree size.

All queries can then be answered in linear time by using the results of the precomputation.

Note: removing the longest suffix can be done by removing the oldest leaf of the suffix tree. It is not easy to implement correctly.

Improve this answer
$\endgroup$
6
  • $\begingroup$ This seems to be a bit off. The task is not to answer all possible $O(n^2)$ queries, but to answer some $q$ given queries. $\endgroup$
    – Gassa
    Jul 4, 2018 at 11:17
  • $\begingroup$ I answered the question for the general case, which was the point of the question. In the special case where the number of queries is low, the solution proposed by the question author would run faster in practice. The number of outputs of a valid solution is $q$, which is of size $O(n^2)$ (disregarding duplicate queries), so any possible solution must run in $O(n^2)$ or slower. My proposed solution takes time $O(n^2)$ for preprocessing and then each query can be answered in constant time. $\endgroup$
    – user11171
    Jul 4, 2018 at 15:10
  • $\begingroup$ Again, $q$ is a parameter. The question is explicitly interested in the number of queries $q$ being $\Theta(n)$, not $\Theta(1)$ nor $\Theta(n^2)$. The answer for $q$ queries is of size $\Theta(q)$ which need not be $\Theta(n^2)$. $\endgroup$
    – Gassa
    Jul 4, 2018 at 15:39
  • $\begingroup$ Why would the number of queries be of order $n$? It seems like an arbitrary condition, if not an oversight by the author. $\endgroup$
    – user11171
    Jul 4, 2018 at 15:46
  • $\begingroup$ The whole problem statement is kind of the same degree of arbitrary. However, this is how a typical data structures problem in competitive programming looks like, so it is unlikely that $n^2$ queries are what the OP looks for. I'd bet $n$ and $q$ are independent parameters from $1$ to $100\,000$ or so, and the time limit is a couple of seconds, so that an $O(nq)$ solution times out, but something better like $O(n \sqrt q)$ doesn't. $\endgroup$
    – Gassa
    Jul 4, 2018 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.