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)

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

See Also

https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm

http://rosettacode.org/wiki/Longest_common_subsequence#Hirschberg_algorithm_version

Meta

Source

See Implementation

nxt lcs functions