class Solution:
    def solve(self, text, patterns):
        # pattern matches
        patpos = []

# intervals
        intervals = []

for i in range(len(text)):

            # find any patterns that match at the start
            for j in range(len(patterns)):
                if text[i] == patterns[j][0]:
                    patpos.append((j, 0))

new_patpos = []

# check if found patterns continue to match
            for j in range(len(patpos)):
                (pat_idx, pos) = patpos[j]
                pattern = patterns[pat_idx]

                if text[i] == pattern[pos]:
                    # next pattern character matches
                    new_pos = pos + 1

if new_pos == len(pattern):
                        # the full pattern matches; save the interval

ival_start = (i - len(pattern)) + 1
                        ival_end = i

intervals.append((ival_start, ival_end))

                    else:
                        # only part of the pattern matches (so far)
                        new_patpos.append((pat_idx, new_pos))

            # roll over patterns that continued to match
            patpos = new_patpos

if len(intervals) == 0:
            return text

# merge intervals
        intervals.sort()
        new_intervals = [intervals[0]]

for i in range(1, len(intervals)):
            (curr_start, curr_end) = intervals[i]
            (prev_start, prev_end) = new_intervals[-1]

if curr_start <= prev_end + 1:
                new_intervals[-1] = (prev_start, max(curr_end, prev_end))
            else:
                new_intervals.append((curr_start, curr_end))

print(new_intervals)

# apply tags
        ans = ''
        ival_idx = 0
        for i in range(len(text)):
            if ival_idx >= len(new_intervals):
                ans += text[i]
            else:
                (ival_start, ival_end) = new_intervals[ival_idx]
                if i == ival_start:
                    ans += '<b>'

ans += text[i]

if i == ival_end:
                    ans += '</b>'
                    ival_idx += 1

return ans