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 (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$: M := ...

Top 50 recent answers are included