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

Optimierungen:

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.



Johannes Waldmann 2007-06-13