This solution based on the problem: 56. Merge Intervals.

Find all the substring of
s
that is in dict, and represents it as an interval[a, b]
, wherea
is the beginning index of the substring andb
is the next of the end of substring. For example,s = "abcxyz123"
,"abc"
is represented as[0, 3]
. 
Merge the above intervals. For example
s = "abcxyz123"
anddict = ["abc","123"]
, the merged intervals is [[0, 3], [6, 9]] 
Insert "<b>" and "<\b>" at the begin and end of each interval.
class Solution {
public:
string addBoldTag(string s, vector<string>& dict) {
vector<pair<int, int>> intervals;
vector<pair<int, int>> res;
// Find intervals
for (string w : dict) {
size_t pos = 0, next = 0;
while ((pos = s.find(w, next)) != string::npos) {
intervals.push_back(make_pair((int)pos, (int)pos + w.size()));
next = pos + 1;
}
}
// Merge intervals
sort(intervals.begin(), intervals.end());
for (int i = 0; i < intervals.size(); i++) {
if (!res.empty() && intervals[i].first <= res.back().second) {
res.back().second = max(intervals[i].second, res.back().second);
} else {
res.push_back(intervals[i]);
}
}
// Insert tags
int offset = 0;
for (auto p : res) {
s.insert(p.first + offset, "<b>");
offset += 3;
s.insert(p.second + offset, "</b>");
offset += 4;
}
return s;
}
};