Алгоритм проверки того, была ли строка построена из списка подстрок

Вам дана строка и массив строк. Как быстро проверить, Если эта строка может быть построена путем объединения некоторых строк в массиве?

Это теоретический вопрос, мне он не нужен по практическим соображениям. Но я хотел бы знать, есть ли для этого какой-нибудь хороший алгоритм.

EDIT Reading some answer I have noticed, that this is probably NP-Complete problem. Even finding a subset of strings, that will together have same length, as a given string is a classic subset sum problem.

So I guess there is no easy answer to this.

EDIT

Now it seems, that it is not a NP-Complete problem after all. That's way cooler :-)

EDIT

I have came up with a solution that passes some tests:

def can_build_from_substrings(string, substrings):
    prefixes = [True] + [False] * (len(string) - 1)
    while True:
        old = list(prefixes)
        for s in substrings:
            for index, is_set in enumerate(prefixes):
                if is_set and string[index:].startswith(s):
                    if string[index:] == s:
                        return True
                    prefixes[index + len(s)] = True
        if old == prefixes: # nothing has changed in this iteration
            return False

I believe the time is O(n * m^3), where n is length of substrings and m is length of string. What do you think?