LCS - eingeschränkt linear

Suche nach einer LCS = Suchen eines kurzen Pfades von (0,0) nach (xs.length-1, ys.length-1).

einzelne Kanten verlaufen

• nach rechts: (i - 1, j)$\to$(i, j)      Buchstabe aus xs
• nach unten: (i, j - 1)$\to$(i, j)      Buchstabe aus ys
• nach rechts unten (diagonal): (i - 1, j - 1)$\to$(i, j)

  gemeinsamer Buchstabe

Optimierungen:

• Suche nur in der Nähe der Diagonalen
• Beginne Suche von beiden Endpunkten

Wenn nur $\le$D Abweichungen vorkommen, dann genügt es, einen Bereich der Größe D ^. N zu betrachten $\Rightarrow$ An O(ND) Difference Algorithm and its Variations.