Структура данных для многократного разбиения строки на более мелкие части

Question

Я пытаюсь написать функцию, которая неоднократно сопоставляет шаблоны регулярных выражений с входной строкой. Функция должна взять шаблон 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"}

(я бы также сохранил ассоциативный массив с информацией о совпадениях / несовпадениях)

Но мои вопросы: какая структура данных будет наиболее подходящей для выполнения такого рода задач? И как это лучше всего решить? Это похоже на то, что будет работать рекурсивно.

Answer 1

Связанный список приходит на ум, когда каждый раз, когда вы сопоставляете регулярное выражение с конкретным узлом, вы удаляете соответствующий узел и вставляете 3 связанных узла на его место.

Конкретная структура "узла" может быть такой же простой, как структура с 3 полями, char* для строки, bool (char в c) для определения совпадения или нет и указатель на следующий узел.