R. Clayton (rclayton@monmouth.edu)
(no date)
Test question 3 describes my solution to the programming assignment. But But,
if it finds any string that completely overlaps with any other string (for
example: oat and boat where boat ends in oat), it merges the two even if the
overlap is not the largest overlap. This test takes care of cases like (abb,
bb, bbc). It will be left with abb and bbc and the compressed string would be
abbc.
You're right - that works when one of the two candidate strings overlaps
completely, but you still have a problem when the two candidate strings both
have non-matching suffixes, as in the strings abb, bbc, and bbd. When it comes
time to choose one of the matching strings, it isn't clear which string you
should chose (at least to me it isn't), and you're back to exhaustive search,
trying all possible candidates to see which one provides more compression.
This is not to say your idea is a bad one; it's just not clear (to me) how to
exploit maximally overlapping strings, although I do believe it's possible to
exploit them.
This archive was generated by hypermail 2.0b3 on Mon May 03 2004 - 17:00:06 EDT