Effizientes Finden eines längsten Substrings

[Matti Mäkitalo]

Hi,

s = der jeweilige String
l = 0
WHILE s nicht leer
  ph = Position des ersten 'h' in s
  IF ph > -1
    s = Teilstring von s ab ph + 1
    pg = Position des ersten 'g' in s
    IF pg > -1
      s = Teilstring von s ab pg + 1
      l = max(l, pg - ph)
    ELSE EXIT
  ELSE EXIT

Wenn ich das richtig sehe, ist die Zuweisung
l = max(l, pg - ph)
falsch. pg ist die Position des ersten g im ("neuindizierten") String s.
Beispiel:
s = "gggggghg"

ph = 7
s = "g"
pg = 0
s = ""
l = max(0, 0 - 7) = 0

Was falsch ist, da die längste "h"-Kette ein Zeichen lang ist.

Martins Lösung dürfte besser sein im Sinne der Effizienz.
Du hast weniger Stringoperationen, da du nur einmal durch den String durchiterieren musst, gleichzeitig brauchst du nur eine Variable für die Länge der aktuellen Zeichenkette, eine für die Länge der bisher Längsten.
Laufzeit O(n) in beiden Fällen, wobei die O-Notation bei dir einen Faktor 4 versteckt (um es mal unfachgemäß auszudrücken), wenn man naiv Stringfunktionen (indexOf, substr) verwendet, die allesamt O(n) ausmachen.

Bis die Tage,
Matti