Mathematics Problem of the Week
Fall 2004
The
string S1 = "ABCDEF" is a subsequence of the string S2 =
"ZABGHFCDQETF" because we can derive S1 from S2 by picking the 2nd,
3rd, 7th, 8th, 10th, and 12th characters from S2 and the ordering (2, 3, 7, 8,
10, 12) is strictly increasing.
The longest common subsequence (LCS) Z of two strings X and Y is a subsequence
of both X and Y and is the longest such subsequence.
What common English word results from finding the LCS of the two strings below?
FBQAZPQNZAZQQNSXA
SBIAXNLEATNTEARS
Hint: remove six letters.
Make sure you explain show how you solved it.
Solutions
should be submitted to Dr. Maegan Bos’ mailbox in the Math office or sent via
e-mail to mbos@stlawu.edu
Presentation counts! The prize-winning entry will
be selected from all correct submissions, based on the clarity, creativity and
elegance of the solution.
Look
for the SLU POW on the Web at http://it.stlawu.edu/~math/activities/