Der längste Teilstring

Wenden wir uns jetzt einer anderen Möglichkeit, das Problem zu lösen.

Man stelle sich vor, daß man eine Textdatei gegeben hat und möchte nun das längst Teilstück dieser Datei finden, das sich wiederholt. Zum Beispiel wäre das in dem Satz "Fischers Fritz fischt frische Fische" das (Teil)Wort 'Fische'.

Man beginnt einfach mit vergleichen von immer zwei Teilstrings. Es wird dafür überpüft, wie viele Zeichen, diese Teile gemeinsam haben. Der längste Teil wird dann ausgegeben.

maxlen = -1
for ( i = 0; i++; i < n)
    for (j = i; j++ ; j < n)
          if (thislen = comlen (&c[i], &c[j])) > maxlen
            maxlen = thislen
            maxi = i
            maxj = j

Die Eingabe liegt im Array c[] vor. Die beiden zu vergleichenden Teile werden an die Funktion comlen() übergeben. Diese berechnte die Anzahl an Zeichen, die die beiden Argumente gemeinsam haben.

int comlen(char *p, char *q)
    i = 0
    while *p && (*p++ == *q++)
          i++
    return i

Da bei diesem Programm jeder Teilstring mit jedem anderen verglichen wird, ergibt sich eine Laufzeit von O(n²). Durch das verwenden einer Hashtabelle wäre ein Verkürzung der Laufzeit möglich.