Find dictionary items whose key matches a substring

[value for key, value in programs.items() if 'new york' in key.lower()]

This is usually called a relaxed dictionary and it can be implemented efficiently using a suffix tree.

The memory used by this approach is linear over the keys, which is optimal, and the time of search is linear over the substring length you are searching, which is also optimal.

I have found this library in python that implements this.

https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/

You should use the brute force method given by mensi until it proves to be too slow.

Here's something that duplicates the data to give a speedier lookup. It only works if your search is for whole words only - i.e. you'll never need to match on "New Yorks Best Bagels" because "york" and "yorks" are different words.

words = {}for key in programs.keys():    for w in key.split():        w = w.lower()        if w not in words:            words[w] = set()        words[w].add(key)def lookup(search_string, words, programs):    result_keys = None    for w in search_string.split():        w = w.lower()        if w not in words:            return []        result_keys = words[w] if result_keys is None else result_keys.intersection(words[w])    return [programs[k] for k in result_keys]

If the words have to be in sequence (i.e. "York New" shouldn't match) you can apply the brute-force method to the short list of result_keys.