While your question is a bit broad, below are some ideas. There isn't a single awesome answer unless you find a free or commercial engine for this that works exactly the way you want.
The way I thought about your problem was to consider the URL as a list of keywords.
- use Lucene as a keyword/tag system. It's good at the types of searches you suggest you want, including phrases, stems, etc.
- store and index the data in DB of choice, but pull the keywords into memory and build a bit index of all keywords vs items. Iterate through the keyword table producing weighted results. If order of keywords matters, you'll also need make a pass through the result set to weight based on word order. These types of searches always need to cap their result set quickly in order to return results quickly.
- cache the results like crazy from working matches, and give precedence to results that users seem to click on the most for a given URL.
- attack the database by using tag indexes in MongoDB. You'd still need to merge and weight results. Very intensive and not likely a good use of DB resources.
- read some of the academic papers on keyword searches. It's a popular topic.
- build a table of words that have dashes in them, and normalize/convert those before running your queries
- always check for full exact matches first