Trova la sottostringa ripetuta più lunga in JavaScript utilizzando le espressioni regolari

Question

Mi piacerebbe trovare la stringa ripetuta più lunga all'interno di una stringa, implementata in JavaScript e utilizzando un approccio basato su espressioni regolari.

Ho un'implementazione PHP che, se diretta su JavaScript, non funziona.

L'implementazione di PHP è preso da una risposta alla domanda "Find longest repeating strings?":

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

Questo popolerà $matches[0][X] (dove X è la lunghezza di $matches[0]) con la stringa ripetendo più lunga trovata in $input. Ho provato questo con molte stringhe di input e ho trovato sicuro che l'output sia corretto.

Il porto più vicino diretta in JavaScript è:

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

Questo non dà risultati corretti

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

io non sono abbastanza familiarità con le espressioni regolari per capire cosa l'espressione regolare usata qui sta facendo.

Esistono sicuramente degli algoritmi che potrei implementare per trovare la sottostringa ripetuta più lunga. Prima che tenti di farlo, spero che una diversa espressione regolare produrrà i risultati corretti in JavaScript.

È possibile modificare l'espressione regolare precedente in modo che l'output previsto venga restituito in JavaScript? Accetto che ciò potrebbe non essere possibile in una sola linea.

Answer 1

Le corrispondenze Javascript restituiscono solo la prima corrispondenza: è necessario eseguire il loop per trovare più risultati. Un po 'di test mostra che questo ottiene i risultati attesi:

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 

Si noti che per "xxabcdyy" si ottiene solo "x" di nuovo, in quanto restituisce la prima stringa di lunghezza massima.

Answer 2

Sembra che le regex di JS siano un po 'strane. Non ho una risposta completa, ma ecco cosa ho trovato.

Sebbene pensassi che facessero la stessa cosa, re.exec() e "stringa" .match (re) si comportano diversamente. Exec sembra restituire solo la prima corrispondenza trovata, mentre la partita sembra restituirle tutte (usando/g in entrambi i casi).

D'altra parte, exec sembra funzionare correttamente con? = Nella regex mentre match restituisce tutte le stringhe vuote. Rimozione del? = Ci lascia con

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

Utilizzando che

"XXinputinputYY".match(re); 

rendimenti

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

mentre

re.exec("XXinputinputYY"); 

rendimenti

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

Quindi almeno con la corrispondenza si ottiene input come uno dei valori. Ovviamente, questo non tira fuori il più lungo, né rimuove la ridondanza, ma forse aiuta comunque.

Un'altra cosa, ho provato nella console di Firebug che ha generato un errore nel non supportare $ 1, quindi forse c'è qualcosa nel $ vars che vale la pena guardare.