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

<p>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. </p>

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

<p>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. </p>

<p>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 </p>

CC BY-SA 3.0
2015-02-15T15:45:12.497Z
Hint: This can be done in $O(|S|^2)$ using dynamic programming.. Doesn't really belong to this site though (see [scope](http://cstheory.stackexchange.com/help/on-topic)).
R B
CC BY-SA 3.0
2015-02-16T16:06:58.470Z
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.
Manuel Lafond
<tree>
Suffix tree and searching for longest subword that appears two times and two occurencies are not overlapping
Krzysztof Lewko
# Suffix tree and searching for longest subword that appears two times and two occurencies are not overlapping

(Asked by: username_0 on 2015-02-15)

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

**Tags:** tree
> **Comments:**
> **username_1**: Hint: This can be done in $O(|S|^2)$ using dynamic programming.. Doesn't really belong to this site though (see [scope](http://cstheory.stackexchange.com/help/on-topic)).  
> **username_2**: 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.  

---

## 0 answers

