What I am looking for is a perl function to be used in a search
engine which would use a flat text file of about 10000 records.
 Given two multi-words strings (a "query" and a "target"), I want to 
get a score number which is proportional to the quality of the match
between query and target. If all the words of the query are in the
target (regardless of order), the score would be 100%. If only parts of
the query word(s) match parts of the target string, a lower score
should be returned. An example of what I want to be able to match is
"waterfall" and "yosemite falls". I am looking for a link to an
existing perl function, as I am sure this problem has been addressed
before several times.

I don't have a link for you, but I'd attack this by generating a list
of substrings of each query word, and then trying to find those in the
target.  The score is then the percentage of substrings that match.

I can see a way to do it by extracting all matching substrings from a
'dictionary' of words you are interested in (eg you would probably like
to exclude all very short words, add some of your own, and what about plurals?)
However what is the longest time you want to provide the scores from your
hypothetical 10000 record file, and what is the length of that file?

I wouldn't want the search to take an unusually long time, 
say more than a couple of seconds. Each record consists of
a short sentence, of an average of less than 10 words. 
When I posted the query, I thought it was a fairly common thing, but
apparently it is not.

I would suggest posting to comp.lang.perl.misc.

You'll get a bunch of comments for free.

Take a look at xapian, it looks close to what you're asking for.  You
can grab a perl front end for in from CPAN ...
http://www.xapian.org/
http://search.cpan.org/search?query=xapian