I'm learning basics of text algorithms, so my question might seem simple.

Let's have word $S$, i want to find longest subword $x$ such that it appears in $S$ two times and those two occurencies are not overlapping.

For example $S=ababab$ and the solution will be $ab$, because any longer subword: $aba$ or $bab$ (or longer) are overlapping.

I came up with one solution: it's using suffix arrays, from that i can calculate LCP (longest common prefix) table and LPF(longest previous factor) table and task is almost done.

Next i tried to solve this task with suffix tree (preferably compressed suffix tree, because uncompressed is almost not used), but i don't really know how to do it. I'd love to hear some solutions from you. Cheers

  • 1
    $\begingroup$ Hint: This can be done in $O(|S|^2)$ using dynamic programming.. Doesn't really belong to this site though (see scope). $\endgroup$
    – R B
    Feb 15 '15 at 15:45
  • 1
    $\begingroup$ Using suffix trees, you can investigate each internal node. If an internal node represents a substring of length $k$, and it has two descendant leaves representing positions $i,j$ such that $|i - j| \geq k$, then the substring occurs at least twice and is not overlapping. I think it's feasible in linear time by just propagating the min/max leaf indices bottom-up. $\endgroup$ Feb 16 '15 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.