1) Just a nit, but usually a string obtained by possibly non adjacent deletions is called a "subsequence," not a "substring." 2) I'll contribute also the following NP-complete problem reference from Garey and Johnson's book (pg 228 in my copy): [SR10] Longest Common Subsequence Instance: Finite alpha \Sigma, finite set R of strings from \Sigma^{*} and a positive integer K. Question: Is there a string w with |w| \geq K such that w is a subsequence of each x \in R? Reference: Transformation from vertex cover [maier, 1978]. Remains NP complete even if |\Sigma| = 2. Solvable in polynomial time for any fixed K or for fixed |R| (by dynamic programming). The analogous longest common substring problem is triviallly solvable in polynomial time Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.plambeck.org ----- Original Message ----- From: "Allan C. Wechsler" <acw@alum.mit.edu> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Saturday, June 12, 2004 10:00 AM Subject: [math-fun] Most repeated longest substring
I'm having a little bit of trouble understanding the problem. It's a matter of how the quantifiers are nested, and how the counting is to be done. I would greatly appreciate it if Neil would go back to Al Aho and get a really clear description of the problem.
My difficulties begin with the definition of f(X,Y). It is not clear that we are permitted to count multiple occurrences of the same substring; it seems equally probable to me that Aho wants to count only subsequences with distinct content. I have other similar hairsplitting problems, but let's start with that one. And ... remember the Al Aho. --ACW
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun