a = '\n'
prefixes = SubstringDict()
for key, value in list(d.items()):
    prefixes[a + key] = value
for query in ['key1', 'key2']:
    pass
More efficient way to look up dictionary values whose keys start with same prefix