koobas.hobune.stream
Longest Common Subsequence Recursive Function Error.
Hi, I have written the following function to calculate the Longest Common Subsequence between two strings:
function lcs(a, b): String {
var aSub = a.Substring(0, a.Length-1);
var bSub = b.Substring(0, b.Length-1);
if (a.Length == 0 || b.Length == 0) {
return "";
} else if (a[a.Length-1] == b[b.Length-1]) {
return lcs(aSub, bSub) + a[a.Length-1];
} else {
var x = lcs(a, bSub);
var y = lcs(aSub, b);
return (x.Length > y.Length) ? x : y;
}
}
However, when I run it, Unity gives me a negative number exception on the second line. On modifying it to say a.Length, Unity crashed. Can someone tell me if this is a problem with Unity handling recursive functions or is my code flawed somewhere.
I essentially have a="start" and b="startblue1stepbgreen2stepgred1stepryellow2stepy". Thus, the function should return "start".
THanks!
I haven't heard of "Longest Common Subsequence". What does that mean?
LCS is something all 2nd year ComSci students know, and no one else :-)
There's a well-known much more efficient non-recursive method involving filling in a 2D array (it unwraps the recursion.) Runs in O(n^2). The recursive version is more like O(2^n).
I'd guess if you tossed in a global `count`, inc'ed it and kicked out at 2,000, (for fun print A and B,) you might just be blowing out the stack.
Hmmm... but then, is there any way I can use this without screwing up the stack? The code works fine if used in an editor.... It's just Unity that's giving me problems...
What I mean is, I'm thinking this approach may run super horribly slow on longer strings, and you may have to rewrite it the "good" way. Try it on two long string w/o much in common.
The problem is actually well known but maybe not under this name ;) A simple code / file-diff program have to solve this to find the differences between two files. LCS
I would have thought that your test on line 4 ought to be of aSub and bSub not of a and b
Or that test should be the first thing that you do before calculating aSub and bSub...
Yes and that's the problem ;) When one of the strings passed to the function has a lenght of 0 you will execute SubString(0,-1) which will cause an ArgumentOutOfRangeException according to the specs of SubString,
