Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged


Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to the suffix tree. Here's pseudocode that finds $M$ - location in the suffix tree that corresponds to $\mathtt{LCS}(S, T)$: M := C := ST.root for i := 1..|T| do ...


The geeksforgeeks solution gives an efficient algorithm that accomplishes the following: Sorts the suffixes of the input string in lexicographic order. For every two adjacent suffixes in this order, finds the longest common prefix. If you are after the number of distinct substrings of length $\ell$, you should proceed as follows: If the first suffix has ...

Top 50 recent answers are included