Definition - Länge der längsten gemeinsamen Teilfolge

• Generalisierungen:
  • Ähnlichkeitsmaß
• Involvierte Definitionen:
  • Zeichenkette
  • Teilfolge
  • siehe auch Levenshtein-Distanz
• Veranstaltung: DM
• Referenz: @valdes2024 (p. 40 f.)

⠀

Definition: Länge der längsten gemeinsamen Teilfolge

Als Länge der längsten gemeinsamen Teilfolge bezeichnen wir ein gängiges Ähnlichkeitsmaß für Zeichenketten.

Dabei ist nach Definition der Teilfolge zu beachten, dass die Zeichen nicht zusammenhängend sein müssen - ihre Reihenfolge darf aber nicht verändert werden.

Das heißt: ist sowohl Teilfolge der Folge und der Folge .

Die Länge der längsten Teilfolge zweier Teilstrings erhalten wir rekursiv durch

Für die Basisfälle setzen wir: