looking for a better way (help with algorithm design)

Hi


Lacking any current projects I've been keeping myself entertained by
working some simple mental exercises. One of the goals is to workout
an optimal c++ solution in terms of time and space, with time taking
precedence, but without allowing an explosion in space requirements
either.


This has turned out to be surprisingly difficult for my current
challenge and I was hoping someone might be able to provide some
insight to break the stalemate.


Problem statement:
Given a textual abbreviation A determine if A is unique across all
keys in the set S; if not provide a list of conflicting keys. An
abbreviation consists of a combination of one or more characters in
the key such that the only restriction placed upon them is they must
appear in order when reading from left to right; characters need not
be consecutive. The solution must scale acceptably when S becomes
nontrivial in size.


This could easily be brute forced by storing S within a vector and
then iterating over each key in S while maintaining a list of those
were A is a valid abbreviation. Obviously not an optimal solution in
time or space.


I thought I had it cold when I came up with using a trie to store the
set of keys to be searched. But then it quickly became apparent that
because the first character of the abbreviation A isn't necessarily
the first character of a key you have no way of knowing where to start
your search within the trie.


Which is what has me stumped. How can I minimize the number of
comparisons required to match an abbreviation to a key without knowing
ahead of time where in the entire character space of the key set the
search needs to begin (remembering that left->right order is
important)??


Another idea that came to mind was an FSM but with anything but a
trivial set of keys its size would be immense accounting for all the
possible starting states. Since then I have been unable to come up
with anything else worth admitting to.


Either I've stumbled upon a truly difficult problem or its so
blatantly obvious that I'm missing the point entirely.


Any suggestions?


Thanks,
Michael

Return to the comp.compilers page.
Search the comp.compilers archives again.