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

Question

Я пытаюсь написать функцию, которая многократно повторяет шаблоны регулярных выражений против входной строки. Функция должна принимать шаблон 1, соответствующий его входной строке, и разделять ее на части совпадающих и несогласованных сегментов. Образец 2 впоследствии будет использоваться на тех несовпадающих сегментах, пока не будут использованы все шаблоны ввода. Тогда аргумент return будет массивом всех подстрок.

Простой пример:

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* для строки, A bool (char в С) в течение, является ли это совпадение или нет, и указатель на следующий узел.