Am I writing a textbook? No. All textbooks suck. (Partly that's because of the unethical rapacious profitable business practices of (most) textbook publishers—these notes will always be freely available. But also, I've never seen a textbook on any topic that I'd be willing to teach from for more than a few weeks; that's why I wrote these notes in the first place.) In particular, if these notes ever became a textbook, they would immediately suck. (Determining whether they already suck is an illuminating exercise for the reader.) Besides, have you ever talked to someone who's actually written a textbook? Do you realize how much work is involved?! No way, man. Not for me.Excellent!
Let LCS(i, j) denote the length of the longest common subsequence of two fixed strings A[1 ..m] and B[1 .. n]. This function can be defined recursively as follows:From which it immediately follows that LCS(i,j) always equals 0. (Presumably the second condition should be 1 + LCS(i-1,j-1).)
LCS(i, j) =
- 0 if i = 0 or j = 0;
- LCS(i-1, j-1) if A[i] = B[j];
- max(LCS(i, j-1), LCS(i-1, j)) otherwise
pwb503 - Metafilter had its very own internet fraud detective... once. (sniff)We didn't just have one. We had nine.
« Older Anthrax Redux.... | Many people have described the... Newer »
This thread has been archived and is closed to new comments
posted by Kwine at 9:02 AM on March 26, 2011 [1 favorite]