# Longest Repeated Substring

**Problem** Find the longest common substring shared within the same word.

**Examples**

```
LRS in AAAAAAAAAA is : AAAAAAAAA
LRS in ABCDEFG is    : No repeated substring
LRS in ABABABA is    : ABABA
LRS in ATCGATCGA is  : ATCGA
```

**Solution**

Assume S = "ABABABA". Begin by building the suffix tree for S.

```
S = A B A B A B A
I = 1 2 3 4 5 6 7
```

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2sxBlNjnzbwuFh5%2FSF_LRS.png?generation=1568003605659847\&alt=media)

Next, return the path label to the deepest *internal* node.

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI2t-xLXJT81KdaLH%2FSF_LRS2.png?generation=1568003605921710\&alt=media)

**Why this works**

As mentioned before, an internal node carries the property that it is shares a common substring with its parent. In addition, it branches out to at least two other occurrences. So the deepest node will not necessarily the longest path label, or the most repeated substring, but the longest substring that is repeated at least 2 times.

A new branch is created per new substring suffix. The deeper into the tree, the more characters are shared with another substring in the tree. Therefore the deepest node will contain the longest shared occurrence.