Match longest repeating sequence (that is not made of a repeating sequence)

Question

Consider the string

aabaabaabaabaab

Clearly this string is made of 5 adjacent occurences of aab, so I want my regex to match aab.

To elaborate: aabaab wouldn't be an acceptable output because it's made by repeating aab. But aab is a valid result because it's not made of a repeated shorter string.

For the sake of the question, let us assume that there can be additional text around the repeated segment (for example 11aabaabaabaabaab22 or even xaabaabaabaabaabaa). Therefore it's not possible to anchor the regex with ^ or $.

---

Failed idea #1: (.+?)\1+ This captures aa instead of the expected aab.

Failed idea #2: (.+)\1+ This captures aabaab.

Is it possible to do this with pure regex? If yes, is it possible without dynamic-width lookbehind?

Answer 1

You can use two lookaheads, the first one searches the longest pattern and the second searches the smallest. The second pattern repeated has to end (at least) at the same position or after the first pattern repeated. To check that, you have to capture the end of the string in the first lookahead and to use a backreference to this capture in the second lookahead.

(?=(.+)\1+(.*))(?=(.+?)\3+\2$)\3+

demo

The result is in the group 3

also:

(?=(.+)\1+(.*))(.+?)\3+(?=\2$)\3*

---

Note that these two regex patterns give the result for one position in a string. If you want to know what is the shortest pattern that is the longest substring once repeated for all the string, you have to find all of them and to select the longest susbstring with code. You can use a pattern for overlapping results to do that:

(?=(.+)\1+(.*))(?=(.+?)\3+\2$)(?=(\3+))

(using the group 4)