文字列を小さな部分に繰り返し分割するためのデータ構造

Question

入力文字列に対してregexpパターンを繰り返し一致させる関数を記述しようとしています。この関数はパターン1を入力文字列と照合し、一致する部分と一致しない部分の部分に分割する必要があります。その後、パターン2は、すべての入力パターンが使用されるまで、一致しないセグメントで使用されます。戻り引数は、すべての部分文字列の配列になります。

簡単な例：

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"}

（私もそれに伴いマッチ/ nonmatch情報との連想配列を続けるだろう）

しかし、私の質問は以下のとおりです。に最も適しているだろうどのようなデータ構造この種のタスクを実行しますか？そして、これはどのようにして解決されるのですか？再帰的に動作するような感じです。

Answer 1

リンクされたリストは、特定のノードに対して正規表現をマッチさせるたびに、問題のノードを削除し、3つのリンクされたノードをその場所に挿入する場所を思いついています。

特定の「ノード」構造は、それが一致しない、または、次のノードへのポインタのかどうかのために3つのフィールド、文字列char*、bool（Cでchar）を有する構造体のように単純であってもよいです。