Algorithmen und Datenstrukturen · Middle · Frage 45 von 75
Was ist die längste gemeinsame Teilfolge (LCS) zweier Strings?
- 1Die längste gemeinsame Folge in Reihenfolge, Lücken erlaubt
- 2Der längste Teilstring, den beide Strings zusammenhängend teilen
- 3Das längste Präfix, mit dem beide Strings beginnen
Antwort zeigen
Richtige Antwort: Die längste gemeinsame Folge in Reihenfolge, Lücken erlaubt
Erklärung
Für „ABCBDAB“ und „BDCABA“ ist eine LCS „BCBA“. Die übliche DP-Tabelle ist O(n × m). LCS ist die Idee hinter diff-Werkzeugen.