Problem #1.

I have 10000 ascii strings (such as perhaps loaded from a file)
A string is input from stdin.
I need to write pseudocode that returns (to stdout) a subset of strings
in the file that contain the same distinct characters (regardless of
order) as input in (input from stdin).
How do I optimize for time.
Assume that this function will need to be invoked repeatedly
For example, if I have strings in the file: mary, brad, pitt, yygr and
the user types in: ry --> the output should be "mary" and "yygr" or if
the user types in: dd --> brad

Problem #2

The whole point is to design a quick lookup to see if a phrase from a
dictionary of phrases occurs inside a user query.

I have a set of 100,000 ascii strings, up to 255 chars each.
Each string has 1 or more words (tokens), space-separated.
A query is input from stdin (1 or more ascii words (tokens),
space-separated)
How towrite pseudocode that determines if the query "soft matches" to
any string from (1). By "soft match", I mean that a contiguous subset
of tokens from the query must match the entirety of the tokens from a
single entry in (1), in the same token order.
How do I optimize for time (this has to process user queries as fast as
possible). For example,
a. if I have strings in (1): mary poppins, brad pitt, yygr
b. and the user types in pictures of brad pitt --the output should be
"true" (because it soft-matches to "brad pitt") or
c. if the user types in: brad --false
d. or if the user types in: brad pitt --true (exactly matches "brad
pitt")
e. or if the user types in: pitt brad pictures --false (right tokens as
in "brad pitt", but wrong order)
f. or if the user types in: brad pitts --false (char match to "brad
pitt", but not a token match)
g. or if the user types in: brad yygr --true (contains "yygr")

Please help

Two words: Regular expression.

--
Bernd


Natasha wrote: