I know how to calculate the lcs of two sequences/strings, however lcs does not need that the subsequence be sequential. I tried it the following way:
Code:
[COLOR=var(--black-800)]function lccs(a, b)[/COLOR]
if a.length == 0 or b.length == 0
return ""
possible = []
if a[0] == b[0]
possible.push(lcs(a[1:), b[1:])
possible.push(lcs(a[1:], b))
possible.push(lcs(a, b[1:)) [COLOR=var(--black-800)] return longest_string(possible)[/COLOR]
longest string returns the longest string in an array, where s[1:] represents a slice of s beginning with the first character.
I've ran this in javascript within a browser and in golang on a remote server, where I put each call to lccs in its own goroutine, but I have no information about the server's hardware specs, thus I have no notion about the parallelization of these routines. I tried reading from this site but couldn't get it right; can someone help?
It ran far too slowly in each of these circumstances.