Effizientes Finden eines längsten Substrings

[Vinzenz Mai]

Hallo,

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.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.

... ist splitten natürlich überflüssig, wenn Finden aller Treffer ausreicht:

  
# Wir durchsuchen den Heuhaufen  
$haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh';  
  
# nach dem Auftreten einer Folge von beliebig vielen,  
# mindestens jedoch einem "h" (der Nadel).  
# Die Gierigkeit von RegExp kommt uns dabei entgegen :-)  
# Nicht beachtet: [link:http://de2.php.net/manual/de/reference.pcre.pattern.modifiers.php@title=UTF-8-Problematik].  
$pattern  = '/h+/';  
  
# Wir bereiten ein Array für das Ergebnis unserer Suche vor.  
$matches  = array();  
  
# und lassen alle Folgen von h finden,  
# alle Treffer sind wegen PREG_PATTERN_ORDER in $matches[0] (einem Array)  
if ([link:http://www.php.net/manual/de/function.preg-match-all.php@title=preg_match_all]($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) {  
    # Wenn kein Fehler auftrat und es Treffer gab  
    [link:http://de2.php.net/manual/de/function.rsort.php@title=rsort]($matches[0], SORT_STRING);   # sortiere von längster nach kürzester  
    echo $matches[0][0];               # und gebe die längste aus  
}  

Problemlos in ein Funktionchen umzubauen, die Heuhaufen und Nadel (der zu suchende Buchstabe) entgegennimmt und die längste Kette zurückgibt.
Ein Ansatz:

  
/*  
    Durchsucht die Zeichenkette $haystack nach dem Muster $pattern und gibt  
    die längste Übereinstimmung zurück. Wird das Muster nicht gefunden, so  
    wird eine leere Zeichenkette zurückgegeben.  
*/  
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;  
}

Aber: Sortieren ist lahm und - wie Martin gezeigt hat - überflüssig.

Freundliche Grüße

Vinzenz