d = {'key1': 'valA', 'key123': 'valB', 'key1XY': 'valC', 'key2': 'valD',
    'key2-22': 'valE'}
a = '\n'
prefixes = SubstringDict()
for key, value in list(d.items()):
    prefixes[a + key] = value
for query in ['key1', 'key2']:
    pass
Более эффективный способ поиска значений словаря, ключи которых начинаются с одного и того же префикса.