Similar::Algorithms::Lcs
LCS diff algorithm.
- time:
O(NM) - space
O(NM)
This is an implementation of the standard longest common subsequence algorithm using dynamic programming. It's primarily here for completeness and will perform worse than both Myers and Patience in pretty much all cases.
Class methods
diff(old, old_range : Range(Int32, Int32), new, new_range : Range(Int32, Int32), d : DiffHook) : Nil
LCS diff algorithm.
Diff old, between indices old_range and new between indices new_range.
diff_deadline(old, old_range : Range(Int32, Int32), new, new_range : Range(Int32, Int32), d : DiffHook, deadline : Similar::DeadlineSupport::Instant | Nil = nil) : Nil
LCS diff algorithm with deadline.
Diff old, between indices old_range and new between indices new_range.
This diff is done with an optional deadline that defines the maximal execution time permitted before it bails and falls back to an approximation.