Znajdź najdłuższy powtarzający się łańcuch w JavaScript za pomocą wyrażeń regularnych

Question

Chciałbym znaleźć najdłuższy powtarzający się ciąg w ciągu znaków, zaimplementowany w JavaScript i przy użyciu metody opartej na wyrażeniu regularnym.

Mam implementację PHP, która po bezpośrednim przeniesieniu do JavaScript nie działa.

Implementacja PHP jest pobierana z odpowiedzią na pytanie "Find longest repeating strings?":

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

To będzie zapełnić $matches[0][X] (gdzie X jest długość $matches[0]) z najdłuższym powtarzając podciągu można znaleźć w $input. Przetestowałem to z wieloma ciągami wejściowymi i znalazłem pewność, że dane wyjściowe są poprawne.

Najbliżej bezpośredni portu w JavaScript jest:

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

To nie daje poprawne wyniki

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

nie jestem na tyle obeznany z wyrażeń regularnych, aby zrozumieć, co wyrażenie regularne używane tutaj to robi.

Istnieją z pewnością algorytmy, które można zastosować, aby znaleźć najdłuższy powtarzający się fragment. Zanim spróbuję to zrobić, mam nadzieję, że inne wyrażenie regularne da prawidłowe wyniki w JavaScript.

Czy powyższe wyrażenie regularne można zmodyfikować tak, aby oczekiwane wyniki były zwracane w JavaScript? Zgadzam się, że może to nie być możliwe w przypadku jednego linera.

Answer 1

Klasyfikacja JavaScript zwraca tylko pierwszy mecz - musisz zapętlić, aby znaleźć wiele wyników. Trochę to pokazuje badanie pobiera oczekiwane rezultaty:

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 

Zauważ, że dla „xxabcdyy” tylko pojawi się znak „X” z powrotem, ponieważ zwraca pierwszy ciąg maksymalnej długości.

Answer 2

Wydaje się, że wyroki JS są nieco dziwne. Nie mam pełnej odpowiedzi, ale oto, co znalazłem.

Chociaż myślałem, że zrobili to samo, re .exec() i "ciąg" .match (re) zachowują się inaczej. Wydaje się, że Exec zwraca tylko pierwszy znaleziony wynik, podczas gdy dopasowanie wydaje się zwracać wszystkie (używając/g w obu przypadkach).

Z drugiej strony, exec wydaje się działać poprawnie z? = W regex podczas gdy match zwraca wszystkie puste ciągi. Wyjmowanie = pozostawia nam

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

Korzystanie że

"XXinputinputYY".match(re); 

powraca

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

natomiast

re.exec("XXinputinputYY"); 

powraca

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

Przynajmniej z dopasowaniem otrzymasz inputinput jako jedną z twoich wartości. Oczywiście, to nie wyciąga najdłuższego, ani nie usuwa nadmiarowości, ale może mimo to pomaga.

Jeszcze jedna rzecz, przetestowałem w konsoli firebug, która spowodowała błąd polegający na tym, że nie wspierałem 1 $, więc być może jest coś, na co warto zwrócić uwagę.