Effizientes Finden eines längsten Substrings

[Vinzenz Mai]

Hallo Gunnar™,

abgesehen davon, dass ich die Vorgehensweise nicht als effizient ansehe ...

ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.

auf das Sortieren sollte man auf jeden Fall verzichten, wenn man nur am größten Wert interessiert ist.

Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.

Wir ersetzen daher das Sortieren in meinem ersten Ansatz

  

> function biggest_substring($pattern, $haystack) {  
>     $result  = '';                     # fürs Ergebnis  
>     $matches = array();                # Zwischenlager  
>     if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) {  
>         rsort($matches[0], SORT_STRING);  
>         $result = $matches[0][0];  
>     }  
>     return $result;  
> }

durch Reduzieren des Arrays auf einen einzigen Wert mittels array_reduce().

Benötigt wird eine Hilfsfunktion, die die längere von zwei Zeichenketten zurückliefert (die Zeichenkette selbst besteht ja aus lauter gleichen Buchstaben):

function rcmp($v, $w) {  
    return strlen($v) > strlen($w) ? $v : $w;  
}  

und schreiben biggest_substring() entsprechend um:

function biggest_substring($pattern, $haystack) {  
    $result  = '';                     # fürs Ergebnis  
    $matches = array();                # Zwischenlager  
    if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) {  
        $result = array_reduce($matches[0], rcmp, '');  
    }  
    return $result;  
}

Damit wird das aufwendige Sortieren auf eine einfache Iteration durch das Ergebnisarray reduziert.

Freundliche Grüße

Vinzenz