Общий подход предлагаю такой. Заводите std::vector<std::vector<std::string>>. Каждый внутренний вектор хранит варианты выбора для очередного куска строки. В частности, для кусков строки между вариативными частями будем считать, что есть всего 1 вариант выбора. Соответственно, весь вектор векторов — это последовательность таких вариативных частей. Задача делится на 2 части:
1. Парсинг входной строки в нашу структуру. Парсим в цикле, вытаскивая из исходной строки по 1 символу, и аккумулируем в промежуточное состояние. Нам понадобится std::string для текущего варианта и std::vector<std::string> для текущей вариативной части.
2. Самое простое, когда наш вектор векторов заполнен, создаём пустой std::string, и накидываем туда из каждого внутреннего вектора по 1 варианту.
