Duplicate substring searching

Question

Is there any efficient way to find the duplicate substring? Here, duplicate means that two same substring close to each other have the same value without overlap. For example, the source string is:

ABCDDEFGHFGH

'D' and 'FGH' is duplicated. 'F' appear two times in the sequence, however, they are not close to each other, so it does not duplicate. so our algorithm will return ['D', 'FGH']. I want to know whether there exists an elegant algorithm instead the brute force method?

Answer 1

It relates to Longest repeated substring problem, which builds Suffix Tree to provide string searching in linear time and space complexity Θ(n)

Answer 2

Not very efficient (suffix tree/array are better for very large strings), but very short regular expression solution (C#):

  string source = @"ABCDDEFGHFGH";

  string[] result = Regex
    .Matches(source, @"(.+)\1")
    .OfType<Match>()
    .Select(match => match.Groups[1].Value)
    .ToArray(); 

Explanation

(.+) - group of any (at least 1) characters
\1   - the same group (group #1) repeated 

Test

  Console.Write(string.Join(", ", result));     

Outcome

  D, FGH

In case of ambiguity, e.g. "AAAA" where we can provide "AA" as well as "A" the solution performs greedy and thus "AA" is returned.