Regex searching for recurring substring with overlap search

user_14912724 0
Viewed 115

"Your goal is to find the longest recurring substring in the input (ignoring case) and returning a lower-case version of that string."

I was solving a little problem, and wanted to use regex, but the expected output overlaps.

My Code:

let x = "Is this thing on?"
console.log((x.match(/(.+)(?=.*\1)/gi)||[]).sort((a,b)=>b.length-a.length)[0].toLowerCase())

Expected answer: "is thi"

My answer: "is th"

Is it possible to solve this problem using regex? If so, how?

javascript regex
2 Answers

The problem here is that the repeated chunk start position occurs before the end of the Group 1 match.

The only thing you can do with regex is capture all overlapping matches of any text that is immediately preceded with this very text that is immediately followed with any one or more text and then this very text again:

/(?=(.*)(?<=(?=.+\1)\1))./sgi

See the regex demo.

Sample implementation in JavaScript:

let x = "Is this thing on?"
console.log(
  (Array.from(x.matchAll(/(?=(.*)(?<=(?=.+\1)\1))/gsi), x=>x[1])||[])
    .sort((a,b)=>b.length-a.length)[0]
    .toLowerCase()
)

user_38329700

I agree with Wiktor, that a pure solution in one regular expression is difficult. My approach was to scan the string several times with a changing regExp:

let res;
for (let l=0,ma;ma="Is this thing on?".match(new RegExp("(?=(.{"+l+"})).+\\1","i"));l++) res=ma[1];
console.log(res.toLowerCase());

It looks for a pattern of length l that is repeated. l is incremented each step of the for loop.

user_26100610
Related