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

Hinweis: Ich gehe hier davon aus, dass Sie jede Teilzeichenkette mehr als einmal verwenden können. Sie können die Lösung verallgemeinern, um diese Einschränkung zu berücksichtigen, indem Sie die Definition von Teilproblemen ändern. Das wird sich negativ auf den Platzbedarf und die erwartete Laufzeit auswirken, aber das Problem bleibt polynomial.

Dies ist ein Problem der dynamischen Programmierung. (Und eine tolle Frage!)

Definieren wir composable(S, W) wahr sein, wenn die Zeichenkette S kann mit Hilfe einer Liste von Teilzeichenfolgen geschrieben werden W .

S zusammensetzbar ist, wenn und nur wenn:

1. S beginnt mit einer Teilzeichenkette w en W .
2. Der Rest der S après w ist ebenfalls zusammensetzbar.

Schreiben wir etwas Pseudocode:

COMPOSABLE(S, W):
  return TRUE if S = "" # Base case
  return memo[S] if memo[S]

  memo[S] = false

  for w in W:
    length <- LENGTH(w)
    start  <- S[1..length]
    rest   <- S[length+1..-1]
    if start = w AND COMPOSABLE(rest, W) :
      memo[S] = true # Memoize

  return memo[S]

Dieser Algorithmus hat eine Laufzeit von O(m*n), vorausgesetzt, die Länge der Teilzeichenketten ist nicht linear zur Zeichenkette selbst. In diesem Fall wäre die Laufzeit O(m*n^2) (wobei m die Größe der Teilzeichenkettenliste und n die Länge der fraglichen Zeichenkette ist). Für die Memoisierung wird O(n) Speicherplatz benötigt.

(Anmerkung: Der Pseudocode verbraucht in seiner jetzigen Form O(n^2) Speicherplatz, aber das Hashing der Memoization Keys würde dieses Problem lösen).

EDIT

Hier ist eine funktionierende Ruby-Implementierung:

def composable(str, words)
  composable_aux(str, words, {})
end

def composable_aux(str, words, memo)
  return true if str == ""                # The base case
  return memo[str] unless memo[str].nil?  # Return the answer if we already know it

  memo[str] = false              # Assume the answer is `false`

  words.each do |word|           # For each word in the list:
    length = word.length
    start  = str[0..length-1]
    rest   = str[length..-1]

    # If the test string starts with this word,
    # and the remaining part of the test string
    # is also composable, the answer is true.
    if start == word and composable_aux(rest, words, memo)
      memo[str] = true           # Mark the answer as true
    end
  end

  memo[str]                      # Return the answer
end

Answer 2

Es geht bestimmt nicht schnell, aber hier ist eine Idee:

• Alle Zeichenketten durchlaufen und prüfen, ob die Zielzeichenkette mit einer von ihnen "beginnt".
• Nehmen Sie die längste Zeichenkette, mit der die Zielzeichenkette beginnt, entfernen Sie sie aus der Liste und schneiden Sie sie aus der Hauptzeichenkette ab
• Ausspülen, wiederholen

Stoppen Sie, wenn Sie eine Zielzeichenkette der Länge 0 erhalten haben.

Wie ich bereits sagte, ist dies definitiv nicht schnell, aber es sollte Ihnen einen Anhaltspunkt geben ("es sollte nicht viel schlimmer werden als das").

EDIT

Wie in den Kommentaren erwähnt, wird dies nicht funktionieren. Sie müssen die Teiltreffer speichern und auf sie zurückgreifen, wenn Sie feststellen, dass es nicht weitergeht.

• Wenn Sie feststellen, dass eine Zeichenkette der Kopf des Ziels ist, schieben Sie sie in eine Liste. Nachdem Sie die Liste erstellt haben, werden Sie natürlich den größten "Kopf" des Ziels ausprobieren
• Wenn du feststellst, dass der Kopf, den du ausprobiert hast, nicht zu dem passt, was übrig ist, versuche den nächstbesten Kopf

Auf diese Weise werden Sie schließlich den gesamten Raum der Lösungen erkunden. Für jeden Kopfkandidaten werden Sie alle möglichen Schwänze ausprobieren.

Answer 3

So würde ich es machen.

1. Bestimmen Sie die Länge der Zielzeichenkette.
2. Bestimmen Sie die Länge jeder Zeichenkette im Teilstring-Array
3. Ermitteln, welche Kombination von Teilzeichenfolgen eine Zeichenkette mit der gleichen Länge wie die Zielzeichenkette ergeben würde (falls vorhanden, falls nicht, sind Sie fertig)
4. Erzeugen Sie alle Permutationen der in Schritt 3 ermittelten Teilzeichenkombinationen. Prüfen Sie, ob eine von ihnen mit der Zielzeichenkette übereinstimmt.

Das Erzeugen aller Permutationen ist eine prozessorlastige Aufgabe. Wenn Sie also Ihr 'n' (Eingabegröße) reduzieren können, gewinnen Sie beträchtliche Effizienz.

Answer 4

Inspiriert durch @cnicutars Antwort:

• Funktion Possible(array A, string s)
  • Si s leer ist, wird true zurückgegeben.
  • das Array zu berechnen P aller Zeichenketten in A die ein Präfix sind von s .
  • Si P leer ist, wird false zurückgegeben.
  • für jede Zeichenkette p en P :
    • wenn Possible(A with p removed, s with prefix p removed) return true
  • return false

Answer 5

Zwei Möglichkeiten kommen mir in den Sinn, aber keine davon scheint sehr elegant zu sein.

1) Brute-Force: machen Sie es wie ein Passwort-Generator, d.h. Wort1+Wort1+Wort1 > Wort1+Wort1+Wort2 > Wort1+Wort1+Wort3 usw. usw.

Der Trick dabei ist die Länge, so dass man alle Kombinationen von 2 oder mehr Wörtern ausprobieren muss, und man weiß nicht, wo man die Grenze setzen kann. Das ist sehr zeitaufwendig.

2) nehmen Sie die Zeichenfolge in Frage und führen Sie eine Suche in auf sie für jedes Wort, das Sie 1 zu einer Zeit haben. vielleicht überprüfen Sie die Länge und wenn seine größer als 0 tun es wieder. halten Sie es tun, bis Sie Null treffen es kann nicht mehr Ergebnisse zu finden. wenn Sie 0 treffen seine ein Gewinn, wenn nicht seine ein verlieren. Ich denke, diese Methode wäre viel besser als die erste, aber ich kann mir vorstellen, dass jemand einen besseren Vorschlag hat.