0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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, 2015 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$
    – Manuel Lafond
    Feb 16, 2015 at 16:06

0

Reset to default

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.

Browse other questions tagged or ask your own question.