Найти самую длинную повторяющуюся подстроку в JavaScript с помощью регулярных выражений

Question

Я хотел бы найти самую длинную повторяющуюся строку в строке, реализованную в JavaScript и использующую подход на основе регулярных выражений.

У меня есть реализация PHP, которая при прямой портировании на JavaScript не 't работа.

Реализация PHP взята из ответа на вопрос "Найти самые длинные повторяющиеся строки?" :

preg_match_all('/(?=((.+)(?:.*?\2)+))/s', $input, $matches, PREG_SET_ORDER);

Это заполнит $matches[0][X] (где X - это длина $matches[0]) с самой длинной повторяющейся подстрокой в ​​$input.Я проверил это со многими входными строками и убедился, что вывод правильный.

Ближайший прямой порт в JavaScript:

var matches = /(?=((.+)(?:.*?\2)+))/.exec(input);

Это не дает правильных результатов

input                  Excepted result   matches[0][X]
======================================================
inputinput             input             input
7inputinput            input             input
inputinput7            input             input
7inputinput7           input             7
XXinputinputYY         input             XX

Я недостаточно знаком с регулярными выражениями, чтобы понять, что делает здесь используемое регулярное выражение.

Конечно, есть алгоритмы, которые я мог бы реализовать, чтобы найти самую длинную повторяющуюся подстроку.Прежде чем я попытаюсь это сделать, я надеюсь, что другое регулярное выражение даст правильные результаты в JavaScript.

Можно ли изменить указанное выше регулярное выражение так, чтобы ожидаемый результат возвращался в JavaScript?Я принимаю, что это может быть невозможно в однострочнике.

Answer 1

Javascript совпадения возвращают только первое совпадение - вы должны выполнить цикл, чтобы найти несколько результатов. Небольшое тестирование показывает, что это дает ожидаемые результаты:

function maxRepeat(input) {
 var reg = /(?=((.+)(?:.*?\2)+))/g;
 var sub = ""; //somewhere to stick temp results
 var maxstr = ""; // our maximum length repeated string
 reg.lastIndex = 0; // because reg previously existed, we may need to reset this
 sub = reg.exec(input); // find the first repeated string
 while (!(sub == null)){
  if ((!(sub == null)) && (sub[2].length > maxstr.length)){
   maxstr = sub[2];
  }
  sub = reg.exec(input);
  reg.lastIndex++; // start searching from the next position
 }
 return maxstr;
}

// I'm logging to console for convenience
console.log(maxRepeat("aabcd"));             //aa
console.log(maxRepeat("inputinput"));        //input
console.log(maxRepeat("7inputinput"));       //input
console.log(maxRepeat("inputinput7"));       //input
console.log(maxRepeat("7inputinput7"));      //input
console.log(maxRepeat("xxabcdyy"));          //x
console.log(maxRepeat("XXinputinputYY"));    //input

Обратите внимание, что для "xxabcdyy" вы возвращаете только "x", поскольку оно возвращает первую строку максимальной длины.

Answer 2

Кажется, регулярные выражения JS немного странные.У меня нет полного ответа, но вот что я нашел.

Хотя я думал, что они делали одно и то же, re.exec () и "string" .match (re) ведут себя по-разному.Кажется, что exec возвращает только первое найденное совпадение, тогда как match возвращает все из них (используя / g в обоих случаях).

С другой стороны, exec, кажется, правильно работает с? = В регулярном выражениитогда как match возвращает все пустые строки.Удаление? = Оставляет нас с

re = /((.+)(?:.*?\2)+)/g

Использование этого

"XXinputinputYY".match(re);

возвращает

["XX", "inputinput", "YY"]

, тогда как

re.exec("XXinputinputYY");

возвращает

["XX", "XX", "X"]

Так что, по крайней мере, при совпадении вы получаете inputinput в качестве одного из ваших значений.Очевидно, что это не вытягивает больше времени и не устраняет избыточность, но, тем не менее, это может помочь.

Еще одна вещь, которую я тестировал в консоли firebug, которая выдавала ошибку об отсутствии поддержки $ 1, поэтому, возможно, что-то есть$ vars стоит посмотреть.