Datenstruktur zum wiederholten Aufteilen einer Zeichenfolge in kleinere Teile

Question

Ich versuche eine Funktion zu schreiben, die wiederholt reguläre Muster mit einer Eingabezeichenfolge vergleicht. Die Funktion sollte Muster 1 mit der Eingabezeichenfolge vergleichen und sie in Teile von übereinstimmenden und nicht übereinstimmenden Segmenten aufteilen. Muster 2 würde anschließend für diese nicht übereinstimmenden Segmente verwendet werden, bis alle Eingabemuster verwendet wurden. Das Rückgabeargument wäre dann ein Array aller Teilstrings.

Einfaches Beispiel:

input string "abcdefgh" against patterns "bc" and "f", would first split it into "a", "bc" and "defgh". Subsequently pattern "f" would be run against the "a" and "defgh" part and splitting the later into "de", "f", and "gh". Return argument {"a", "bc", "de", "f", "gh"}

(Ich würde auch mit Spiel/Nicht-Übereinstimmungs Informationen zusammen mit ihm ein assoziatives Array halten)

Aber meine Fragen sind: Welche Datenstruktur am besten geeignet wäre zu diese Art von Aufgabe durchführen? Und wie wäre das am besten zu lösen? Es fühlt sich an wie etwas, das rekursiv funktioniert.

Answer 1

Eine verkettete Liste kommt in den Sinn, wenn Sie bei jeder Übereinstimmung einer Regex mit einem bestimmten Knoten den betreffenden Knoten entfernen und stattdessen 3 verknüpfte Knoten einfügen.

Die besondere „node“ Struktur könnte mit 3 Feldern als struct so einfach sein, ein char* für die Schnur, ein bool (char in c), ob es eine Übereinstimmung gibt oder nicht, und den Zeiger auf den nächsten Knoten.