bold strings

class PolyHash():
    def __init__(self, seq: List[int], prime=37, rem=10**9+7):
        n = len(seq)
        self.rem = rem
        self.hashes = [0]*(n+1)
        self.pows = [1]*(n+1)
        for i in range(1, n+1):
            self.pows[i] = self.pows[i-1]*prime % rem
            self.hashes[i] = (self.hashes[i-1]*prime + seq[i-1]) % rem

    def hash(self, l: int, r: int):
        ''' [l, r) '''
        return (self.hashes[r] - (self.hashes[l]*self.pows[r-l]) % self.rem) % self.rem

def string_hasher(s: string) -> PolyHash:
    return PolyHash([ord(ch)-ord('a') for ch in s])

def calc_word_hashes(words: List[str]) -> List[int]:
    word_hashes = [None]*len(words)
    for i, word in enumerate(words):
        word_hasher = string_hasher(word)
        word_hashes[i] = word_hasher.hash(0, len(word))
    return word_hashes

def scanline(bolds: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    START, END = 0, 1
    pois = [(start, START) for start, _ in bolds] + [(end, END) for _, end in bolds]
    pois.sort()

    n_opened = 0
    b_start = None
    res = []
    for x, tip in pois:
        if tip == START:
            if n_opened == 0:
                b_start = x
            n_opened += 1
        else:
            n_opened -= 1
            if n_opened == 0:
                res.append((b_start, x))

    return res

class Solution:
    def boldWords(self, words: List[str], s: str) -> str:
        word_hashes = calc_word_hashes(words)
        s_hasher = string_hasher(s)
        bolds = []
        for i in range(1, len(s)+1):
            for j, h in enumerate(word_hashes):
                if i >= len(words[j]):
                    if s_hasher.hash(i-len(words[j]), i) == h:
                        bolds.append((i-len(words[j]), i))

        bolds = scanline(bolds)
        res = []
        j, k = 0, 0
        for i in range(len(s)+1):
            if j < len(bolds) and bolds[j][k] == i:
                if k == 0:
                    res.append("<b>")
                    k += 1
                else:
                    res.append("</b>")
                    k = 0
                    j += 1

            if i < len(s):
                res.append(s[i])

        return ''.join(res)