Эффективные строки, содержащие друг друга

У меня есть два набора строк (A и B), и я хочу узнать все пары строк a в A и b в B, где a является подстрокой b.

Первый шаг кодирования был следующим:

for a in A:
    for b in B:
        if a in b:
            print (a,b)

Однако, я хотел узнать, есть ли более эффективный способ сделать это с помощью регулярных выражений (например, вместо проверки if a in b:, проверьте, совпадает ли regexp '.*' + a + '.*': с 'b'. Я подумал, что, возможно, использование чего-то подобного позволит мне кэшировать функцию отказа Knuth-Morris-Pratt для всех a. Кроме того, использование понимания списка для внутреннего цикла for b in B:, вероятно, даст довольно большое ускорение (а понимание вложенного списка может быть еще лучше).

Меня не очень интересует гигантский скачок в асимптотическом времени работы алгоритма (например, использование суффиксного дерева или чего-то еще сложного и умного). Меня больше волнует константа (мне просто нужно сделать это для нескольких пар множеств A и B, и я не хочу, чтобы это работало всю неделю).

Знаете ли вы какие-нибудь хитрости или у вас есть общие советы, чтобы сделать это быстрее? Большое спасибо за любое понимание, которым вы можете поделиться!

Edit:

Используя советы @ninjagecko и @Sven Marnach, я построил быструю таблицу префиксов 10-меров:

    import collections
    prefix_table = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i in xrange(len(prot_seq)-10):
            j = i+10+1
            prefix_table[b[i:j]].add(k)

    for a in A:
        if len(a) >= 10:
            for k in prefix_table[a[:10]]:
                # check if a is in b
                # (missing_edges is necessary, but not sufficient)
                if a in B[k]:
                    print (a,b)
        else:
            for k in xrange(len(prots_and_seqs)):
                # a is too small to use the table; check if
                # a is in any b
                if a in B[k]:
                    print (a, b)