lcs

Longest Common Subsequence (LCS) using Hirschberg. Linear-Space Faster Dynamic Programming Version.

Time Complexity: O(m*n) Space Complexity: O(min(m,n))

To speed up this code on DMD remove the memory allocations from lcsLengths, and do not use the retro range (replace it with foreach_reverse)

  1. const(T)[] lcs(T[] xs, T[] ys)
    pure
    const(T)[]
    lcs
    (
    T
    )
    (
    in T[] xs
    ,
    in T[] ys
    )
  2. string lcs(string a, string b)

See Also

Meta