25 Sep 2001 00:16:08 -0400

Related articles |
---|

looking for a better way (help with algorithm design) mcr+usenet@yuck.net (Michael Roach) (2001-09-25) |

Re: looking for a better way (help with algorithm design) mcr+usenet@yuck.net (Michael Roach) (2001-09-25) |

Re: looking for a better way (help with algorithm design) Georg.Bisseling@pallas.com (Georg Bisseling) (2001-09-29) |

From: | "Michael Roach" <mcr+usenet@yuck.net> |

Newsgroups: | comp.compilers |

Date: | 25 Sep 2001 00:16:08 -0400 |

Organization: | Compilers Central |

Keywords: | question |

Posted-Date: | 25 Sep 2001 00:16:08 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.