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

Es scheint mir, dass das Problem durch einfaches lineares Traversieren des Arrays und Vergleich gelöst werden kann. Allerdings könnte es mehrere Durchläufe geben. Sie können sich eine Strategie ausdenken, um die Durchläufe zu minimieren. Zum Beispiel kann man im ersten Durchgang ein Sub-Array mit allen Teilzeichenfolgen der ursprünglichen Zeichenkette erstellen. Dann probieren Sie verschiedene Variationen linear aus.

Answer 2

Hier ist eine grobe Idee, die funktionieren sollte.

1. Kopieren der Quellzeichenkette in eine neue Zeichenkette
2. Solange die kopierte Zeichenfolge noch Daten enthält und noch Teilzeichenfolgen vorhanden sind a. Einen Teilstring nehmen, wenn copy.contains(substr) copy.remove(substr)
3. Wenn die Kopie nun leer ist, können Sie die Zeichenkette so konstruieren
4. Wenn copy nicht leer ist, wird das erste Substrat, das aus der Zeichenkette entfernt wurde, verworfen und der Vorgang wiederholt.
5. Wenn alle Teilzeichenketten verschwunden sind und die Kopie immer noch nicht leer ist, können Sie sie nicht konstruieren.

Bearbeiten: Eine Möglichkeit, dies zu verbessern, bestünde darin, zunächst alle Teilzeichenketten zu iterieren und alle herauszuwerfen, die nicht in der Hauptzeichenkette enthalten sind. Dann gehen Sie durch die oben genannten Schritte.

Answer 3

Wenn jede Teilzeichenkette nur einmal verwendet werden darf, aber nicht alle verwendet werden müssen...

Für jede Permutation der Größe N aus den Teilzeichenketten, die gleich groß ist wie die ursprüngliche Zeichenkette, prüfen Sie diese, wenn es keine gibt, führen Sie eine Permutation von N+1 Elementen durch, und so weiter, bis Sie alle Permutationen ausgeschöpft haben.

Natürlich ist NP komplett, verdammt langsam, aber ich denke, dass es keine normalen Lösungen gibt.

Zu erklären, warum die Lösungen, bei denen Teilzeichenfolgen aus der ursprünglichen Zeichenkette entfernt werden, niemals funktionieren:

Sie haben eine Zeichenkette "1234123" und ein Array "12", "34", "123". Wenn Sie "123" am Anfang entfernen, haben Sie ein falsches Negativ. Ein ähnliches Beispiel, bei dem das Ende entfernt wird, wäre: "1234123" : "23, "41", "123".

Bei Backtracking mit Greedy: (m Stringlänge 7, n num Elemente 3) - nimm die längste: 123 - entferne es vom ersten Vorkommen O(3) - versuche die anderen beiden mit dem Rest: no go + O((n-1)*(m-3)) - zurückverfolgen O(1) - entferne es vom zweiten: O(m-3) - versuche die anderen beiden O((n-1)*m-3) = O(30)

Permutationen von 1 + 2 + 3 = O(3) + O(4) + O(6) = O(13). Für kleine Teilmengen sind Permutationen also tatsächlich schneller als Backtracking. Dies ändert sich, wenn Sie viele Teilmengen suchen (in den meisten, aber nicht allen Fällen).

Sie können nur die nicht vorhandenen Teilzeichenfolgen aus dem Array entfernen, um die Anzahl der Permutationen von n^n auf n^(n-1) für jede entfernte nicht vorhandene Teilzeichenfolge zu verringern.

Answer 4

Ich schlage die Verwendung von Suffixbäumen vor (unter Verwendung des Online-Algorithmus von Ukkonen), die für die Suche nach gemeinsamen Teilzeichen in zwei Texten geeignet zu sein scheinen. Weitere Informationen finden Sie in wikipedia/special sources. Die Aufgabe lautet

Find all z occurrences of the patterns P1..Pn of total length m
enter code hereas substrings in O(m + z) time.

Sie sehen also, es gibt eine sehr gute Lösung. Ich hoffe, dass diese Lösung für Sie funktionieren wird. Dies ist eigentlich mehr geeignet für wiederholte Scans, als ein einzelner Scan.

Answer 5

Was Sie suchen, ist ein Parser. Ein Parser prüft, ob ein bestimmtes Wort zu einer bestimmten Sprache gehört. Ich bin mir nicht sicher, wie kompliziert die Berechnung Ihres Problems genau ist. Einiges von dem, was oben gesagt wurde, scheint richtig zu sein (es besteht überhaupt keine Notwendigkeit für eine erschöpfende Suche). Eines ist sicher, es ist nicht NP-komplett.

Das Alphabet Ihrer Sprache besteht aus allen kleinen Teilzeichen. Das Wort, das Sie suchen, ist die Zeichenfolge, die Sie haben. Ein regulärer Ausdruck kann ein einfacher Kleene-Stern oder eine sehr einfache kontextfreie Grammatik sein, die nichts anderes als Ors enthält.

Das Hauptproblem des Algorithmus ist: Was ist, wenn einige der Teilzeichenketten tatsächlich Teilzeichenketten zu anderen Teilzeichenketten sind ... das heißt, was ist, wenn wir Teilzeichenketten haben: "ab", "abc", "abcd", ... In diesem Fall ändert die Reihenfolge der Prüfung der Teilzeichenfolgen die Komplexität. Hierfür gibt es LR-Parser. Ich denke, sie sind am besten geeignet, solche Probleme zu lösen.

Ich werde Ihnen die genaue Lösung bald mitteilen.