Encuentra la subcadena repetitiva más larga en JavaScript con las expresiones regulares

Question

Me gustaría encontrar la cadena repetitiva más larga dentro de una cadena, implementada en JavaScript y utilizando un enfoque basado en expresiones regulares.

Tengo una implementación de PHP que, cuando se transfiere directamente a JavaScript, no funciona.

La aplicación PHP es tomada de una respuesta a la pregunta "Find longest repeating strings?":

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

Esto llenará $matches[0][X] (donde X es la longitud de $matches[0]) con la subcadena más larga de repetición que se encuentran en $input. He probado esto con muchas cadenas de entrada y he encontrado que estoy seguro de que la salida es correcta.

El puerto más cercano directa en JavaScript es:

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

Esto no da resultados correctos

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

No soy lo suficientemente familiarizado con las expresiones regulares para entender lo que la expresión regular utiliza aquí está haciendo.

Ciertamente hay algoritmos que podría implementar para encontrar la subcadena repetitiva más larga. Antes de intentar hacer eso, espero que una expresión regular diferente produzca los resultados correctos en JavaScript.

¿Se puede modificar la expresión regular anterior para que el resultado esperado se devuelva en JavaScript? Acepto que esto puede no ser posible en un one-liner.

Answer 1

Las coincidencias Javascript solo devuelven la primera coincidencia: debe realizar un bucle para encontrar resultados múltiples. Una pequeña muestra de pruebas este obtiene los resultados esperados:

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 

Tenga en cuenta que para "xxabcdyy" que sólo recibe "x" de nuevo, ya que devuelve la primera cuerda de longitud máxima.

Answer 2

Parece que las expresiones regulares de JS son un poco raras. No tengo una respuesta completa, pero esto es lo que encontré.

Aunque pensé que hicieron lo mismo, re.exec() y "cadena" .match (re) se comportan de manera diferente. Parece que Exec solo devuelve la primera coincidencia que encuentra, mientras que match parece devolverlos a todos (usando/g en ambos casos).

Por otro lado, parece que exec funciona correctamente con? = En la expresión regular, mientras que la coincidencia devuelve todas las cadenas vacías. Extracción de la? = Nos deja con

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

Usando esa

"XXinputinputYY".match(re); 

vuelve

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

mientras que

re.exec("XXinputinputYY"); 

vuelve

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

De modo que al menos con la coincidencia puede obtener la entrada de entrada como uno de sus valores. Obviamente, esto no dura más tiempo ni elimina la redundancia, pero tal vez sea útil.

Otra cosa, probé en la consola de Firebug que arrojó un error acerca de no admitir $ 1, así que tal vez haya algo en los $ vars que vale la pena mirar.