Algorithmus zur Überprüfung, ob eine Zeichenkette aus einer Liste von Teilzeichenfolgen gebildet wurde

Question

Sie erhalten eine Zeichenkette und ein Array von Zeichenketten. Wie kann man schnell prüfen, ob diese Zeichenkette durch Verkettung einiger Zeichenketten im Array gebildet werden kann?

Dies ist eine theoretische Frage, ich brauche sie nicht aus praktischen Gründen. Aber ich würde gerne wissen, ob es einen guten Algorithmus für diese Aufgabe gibt.

EDIT Beim Lesen einiger Antworten habe ich festgestellt, dass es sich wahrscheinlich um ein NP-komplettes Problem handelt. Selbst das Finden einer Teilmenge von Zeichenketten, die zusammen die gleiche Länge haben wie eine gegebene Zeichenkette, ist ein klassisches Teilmengensummenproblem.

Es gibt also wohl keine einfache Antwort auf diese Frage.

EDIT

Nun scheint es, dass es sich doch nicht um ein NP-komplettes Problem handelt. Das ist viel cooler :-)

EDIT

Ich habe eine Lösung gefunden, die einige Tests bestanden hat:

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

Ich glaube, die Zeit ist reif O(n * m^3) donde n ist die Länge von substrings y m ist die Länge von string . Was meinen Sie dazu?

Answer 1

Ich habe mir dafür einen One-Liner ausgedacht, der die Prinzipien der dynamischen Programmierung nutzt. Die Funktion foo nimmt eine Zeichenkette und eine Liste von Teilzeichenketten, um zu entscheiden, ob es möglich ist, die gegebene Zeichenkette aus der gegebenen Liste zu konstruieren

foo = lambda s, arr:  not s or any(foo(s[len(n):], arr) for n in arr if s[:len(n)]==n)

Der One-Liner zur besseren Lesbarkeit aufgeschlüsselt:

def foo(s, arr):
if not s: return True
for sub in arr:
    if s[:len(sub)] == sub:
        if foo(s[len(sub):], arr):
            return True
return False